本文主要是介绍poj 1144 Network（割点），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://poj.org/problem?id=1144
题意很简单，已知图中各边的连接情况，求割点的个数。
注意输入格式。。
#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;vector<int> edge[110];
int dfn[110];//记录节点被访问的深度
int vis[110];//记录该节点当前的状态，0表示未访问，1表示在栈中，2表示已经访问过
int low[110];//该节点可以到达的访问时间最早的祖先
int n;
int root;//根节点编号
int sum;//割点个数
int ok[110];//在深度遍历过程中，记录每个节点的深度，对当前节点s以及和它相连的节点t，有以下两种情况：
//t没被访问过，这时递归节点t，并用t通过非树枝边可以到达的最早的祖先来更新s的low值；
//t当前在栈中，这时说明图中有一个环，用t的深度来更新s的low值，
//s是割点的条件：s是根且有大于一个的儿子(用son来计数)，或s不是根，且s有一个儿子i满足low[i] >= dfn[s];
void dfs(int s, int father, int dep)
{int son = 0;vis[s] = 1;dfn[s] = low[s] = dep;for(int i = 0; i < (int)edge[s].size(); i++){int t = edge[s][i];if(vis[t] == 1 && t != father)low[s] = min(low[s],dfn[t]);if(vis[t] == 0){dfs(t,s,dep+1);son++;low[s] = min(low[s],low[t]);if((s == root && son > 1) ||(s != root && dfn[s] <= low[t]))ok[s] = 1;}}vis[s] = 2;
}int main()
{int u,v;while(~scanf("%d",&n) && n){for(int i = 1; i <= n; i++)edge[i].clear();memset(dfn,0,sizeof(dfn));memset(vis,0,sizeof(vis));memset(low,0,sizeof(low));memset(ok,0,sizeof(low));sum = 0;while(~scanf("%d",&u) && u){while(getchar() != '\n'){scanf("%d",&v);edge[u].push_back(v);edge[v].push_back(u);}}root = 1;dfs(1,-1,1);for(int i = 1; i <= n; i++)if(ok[i])sum++;printf("%d\n",sum);}return 0;
}
这篇关于poj 1144 Network（割点）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
