POJ 1144 Network —— （找割点）

　　这是一题找无向图的割点的模板题，割点的概念什么的就不再赘述了。这里讲一下这个模板的一个注意点。

　　dfs中有一个child，它不等于G[u].size()！理由如下：

　　如上图，1的size是2，但是它的child是1，因为对他进行dfs时，顺序是1-2-3...然后再等到它访问它的第二个节点3时，3已经被访问过了，不能算他的child了，这是一个误区。

　　代码如下：

 1 #include <stdio.h>
 2 #include <stack>
 3 #include <algorithm>
 4 #include <string.h>
 5 #include <vector>
 6 using namespace std;
 7 
 8 const int N = 100+5;
 9 
10 stack<int> S;
11 int scc_cnt;
12 int dfs_clock;
13 int dfn[N];
14 int low[N];
15 int iscut[N];
16 vector<int> G[N];
17 
18 void dfs(int u,int fa)
19 {
20     dfn[u]=low[u]=++dfs_clock;
21     int child = 0;
22     for(int i=0;i<G[u].size();i++)
23     {
24         int v = G[u][i];
25         if(!dfn[v])
26         {
27             child++;
28             dfs(v,u);
29             low[u]=min(low[u],low[v]);
30             if(low[v]>=dfn[u]) iscut[u]=1;
31         }
32         else if(dfn[v]<dfn[u] && v!=fa)
33         {
34             low[u]=min(low[u],dfn[v]);
35         }
36     }
37     if(fa == -1 && child == 1) iscut[u]=0;
38 }
39 
40 int main()
41 {
42     int n;
43     while(scanf("%d",&n)==1 && n)
44     {
45         memset(dfn,0,sizeof(dfn));
46         memset(iscut,0,sizeof(iscut));
47         dfs_clock=0;
48         for(int i=1;i<=n;i++) G[i].clear();
49         
50         int x;
51         while(scanf("%d",&x)==1 && x)
52         {
53             while(getchar() != '
')
54             {
55                 int y;
56                 scanf("%d",&y);
57                 G[x].push_back(y);
58                 G[y].push_back(x);
59             }
60         }
61 
62         dfs(1,-1);
63         int cnt=0;
64         for(int i = 1 ;i<=n;i++) if(iscut[i]) cnt++;
65         printf("%d
",cnt);
66     }
67     return 0;
68 }