SPF(poj 1523) 割点入门

 1 /*****************************************
 2     SPF(poj 1523)
 3     割点入门
 4     http://poj.org/problem?id=1523
 5 
 6 ******************************************/
 7 
 8 #include<iostream>
 9 #include<algorithm>
10 #include<cstdio>
11 #include<cstring>
12 #include<vector>
13 using namespace std;
14 
15 const int M=1005;
16 vector<int>g[M];
17 int dfn[M],low[M];
18 int vs[M],num[M];
19 int dfs_cut;
20 
21 void Init()
22 {
23     for (int i=0;i<M;i++) g[i].clear();
24     memset(dfn,0,sizeof(dfn));
25     memset(low,0,sizeof(low));
26     memset(vs,0,sizeof(vs));
27     memset(num,0,sizeof(num));
28     dfs_cut=0;
29 }
30 
31 void dfs(int u)
32 {
33     vs[u]=1;
34     low[u]=dfn[u]=++dfs_cut;
35     for (int i=0;i<g[u].size();i++)
36     {
37         int v=g[u][i];
38         if (!vs[v])
39         {
40             dfs(v);
41             low[u]=min(low[u],low[v]);
42             if (low[v]>=dfn[u]) num[u]++;
43         }
44         else low[u]=min(low[u],dfn[v]);
45     }
46 }
47 
48 int main()
49 {
50    int u,v,k=1;
51    while (cin>>u&&u)
52    {
53        Init();
54        cin>>v;
55        g[u].push_back(v);
56        g[v].push_back(u);
57        while (cin>>u&&u)
58        {
59            cin>>v;
60            g[u].push_back(v);
61            g[v].push_back(u);
62        }
63        dfs(1);
64        if (num[1]) num[1]--;        ///num记录孩子的个数，但1就没有父亲，所以就让它-1，最后输出同一加1
65                                     ///感觉num[i]>0是一定的，但是不判断会出错，也许有1 1这组数据吧。
66        printf("Network #%d
",k++);
67        int flag=1;
68        for (int i=1;i<M;i++)
69        {
70            if (num[i])
71            {
72                printf("  SPF node %d leaves %d subnets
",i,num[i]+1);
73                flag=0;
74            }
75        }
76        if (flag) printf("  No SPF nodes
");
77        printf("
");
78    }
79 }