poj 1144 Network(割点入门）

http://poj.org/problem?id=1144
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<vector>
 5 using namespace std;
 6 
 7 const int mx=105;
 8 vector<int>map[mx];
 9 int dfn[mx],low[mx],vs[mx],flag[mx];
10 int dfn_cut;
11 
12 void dfs(int v,int u)
13 {
14     int child=0;
15     dfn[v]=low[v]=++dfn_cut;
16     vs[v]=1;
17     for (int i=0;i<map[v].size();i++)
18     {
19         int w=map[v][i];
20         if (!vs[w])
21         {
22             child++;
23             dfs(w,v);
24             low[v]=min(low[v],low[w]);
25             if (child>1&&v==1) flag[v]=1;
26             if (v!=1&&low[w]>=dfn[v]) flag[v]=1;
27         }
28         else if (w!=u&&u!=-1) low[v]=min(low[v],dfn[w]);
29     }
30 }
31 
32 int main()
33 {
34     int n,x,y;
35     while (~scanf("%d",&n)&&n)
36     {
37         for (int i=1;i<=n;i++) map[i].clear();
38         while (~scanf("%d",&x)&&x)
39         {
40             char c;
41             while (c=getchar()!='
')
42             {
43                 scanf("%d",&y);
44                 map[x].push_back(y);
45                 map[y].push_back(x);
46             }
47         }
48         memset(low,0,sizeof(low));
49         memset(dfn,0,sizeof(dfn));
50         memset(vs,0,sizeof(vs));
51         memset(flag,0,sizeof(flag));
52         dfn_cut=0;
53         dfs(1,-1);
54         int ans=0;
55         for (int i=1;i<=n;i++) ans+=flag[i];
56         printf("%d
",ans);
57     }
58 }
终于做了一道割点题，虽然还不太懂