POJ 1144 Network（无向图的割顶和桥模板题）

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 using namespace std;
11 
12 const int maxn=100+5;
13 
14 int n;
15 vector<int> G[maxn];
16 int pre[maxn],low[maxn];
17 int iscut[maxn];
18 int dfs_clock;
19 
20 int dfs(int u,int fa)
21 {
22     int lowu=pre[u]=++dfs_clock;
23     int child=0;
24     for(int i=0;i<G[u].size();i++)
25     {
26         int v=G[u][i];
27         if(!pre[v])
28         {
29             child++;
30             int lowv=dfs(v,u);
31             lowu=min(lowu,lowv);
32             if(lowv>=pre[u])  iscut[u]=true;
33         }
34         else if(pre[v]<pre[u] && v!=fa)
35             lowu=min(lowu,pre[v]);
36     }
37     if(fa<0&&child==1)  iscut[u]=0;
38     low[u]=lowu;
39     return lowu;
40 }
41 
42 int get_int(char s[])
43 {
44     int m=0;
45     for(int i=0;s[i];i++)
46         m=m*10+s[i]-'0';
47     return m;
48 }
49 
50 int main()
51 {
52     //freopen("D:\input.txt","r",stdin);
53     while(~scanf("%d",&n) && n)
54     {
55         for(int i=1;i<=n;i++)  G[i].clear();
56         memset(pre,0,sizeof(pre));
57         memset(low,0,sizeof(low));
58         memset(iscut,0,sizeof(iscut));
59         dfs_clock=0;
60 
61         char s[5];
62         while(scanf("%s",&s))
63         {
64             if(s[0]=='0')  break;
65             int u=get_int(s);
66             while(scanf("%s",&s))
67             {
68                 int v=get_int(s);
69                 G[u].push_back(v);
70                 G[v].push_back(u);
71                 if(getchar()=='
')   break;
72             }
73         }
74         int ans=0;
75         dfs(1,-1);
76         for(int i=1;i<=n;i++)
77             if(iscut[i])  ans++;
78         printf("%d
",ans);
79     }
80     return 0;
81 }