POJ 1144 Network

浏览数：25 / 时间：2015年06月09日

题目大意的本质就是给你一个图，求该图的割点个数。

不过这一题的输入有点特别，以第二个例子为例：

6（输入的第一个数，表示节点个数，0代表结束输入）
2 1 3（第一个数代表节点（以2为例，0代表结束边的输入），第二个数到后面的所有数字代表与节点2相邻的边）（这组代表有边2-1 和2-3）
5 4 6 2（同上）
0（结束输入）
这道题是典型的求图的割点。
分析：求图的割点要用到两个函数：dfn,low.
dfn[v]代表无向图中节点v的先序值（也就是DFS树中遍历的顺序，也就是v的发现时间。
low[v]代表节点v及其后代所能追溯到的最早的（最先被发现）祖先点u的dfn[u]的值。
求割点基于这样的事实：
事实一：如果u不是根，u成为割点当且仅当存在u的某个儿子节点v,从v或者v的后代到点u的祖先点之间不存在后向边。
事实二：如果u为根，则u成为割点当且仅当他有不止一个儿子节点。
贴上代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #define MAX 110
 5 #define Min(a,b) a<b ? a : b
 6 using namespace std;
 7 int n,m,ans,din,s;
 8 bool map[MAX][MAX],use[MAX];
 9 int dfn[MAX],low[MAX];
10 void init()
11 {
12     int u,v;
13     memset(map,false,sizeof(map));
14     while(scanf("%d",&u) && u){
15         char x;
16         while(1){
17             scanf("%d",&v);
18             scanf("%c",&x);
19             map[u][v]=map[v][u]=true;
20             if(x==‘\n‘) break;
21         }
22     }
23 }
24 void tarjan(int k)
25 {
26     dfn[k]=low[k]=++din;
27     for(int i=1;i<=n;i++)
28     if(map[k][i]){
29         if(dfn[i]==0) {
30             tarjan(i);
31             low[k]=Min(low[k],low[i]);
32             if(low[i]>=dfn[k] && !use[k]){
33                 if(k>1) {ans++;use[k]=true;}
34                 else s++;
35             }
36         }
37         else low[k]=Min(low[k],dfn[i]);
38     }
39 }
40 void solve()
41 {
42     memset(dfn,0,sizeof(dfn));
43     memset(low,0,sizeof(low));
44     memset(use,false,sizeof(use));
45     ans=din=s=0;
46     tarjan(1);
47     if(s>1) ans++;
48     printf("%d\n",ans);
49 }
50 int main()
51 {
52     while(scanf("%d",&n) && n>0){
53         init();
54         solve();
55     }
56     return 0;
57 }