Posted on 2008-04-09 09:32
superman 閱讀(319)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1119 C++ 00:00.03 1832K */
2 #include <iostream>
3
4 using namespace std;
5
6 const int N = 1001;
7
8 int maxTo; bool map[N][N];
9 int low[N], visited[N], subset[N], cnt;
10
11 void dfs(int u)
12 {
13 low[u] = visited[u] = ++cnt;
14 for(int v = 1; v <= maxTo; v++)
15 if(map[u][v])
16 {
17 if(visited[v] == 0)
18 {
19 dfs(v);
20 low[u] <?= low[v];
21 if(low[v] >= visited[u])
22 subset[u]++;
23 }
24 else
25 low[u] <?= visited[v];
26 }
27 }
28
29 int main()
30 {
31 int s, t, network = 0;
32 cin >> s;
33 while(s)
34 {
35 maxTo = 0, cnt = 0;
36 memset(map, false, sizeof(map));
37 memset(low, 0, sizeof(low));
38 memset(visited, 0, sizeof(visited));
39 memset(subset, 0, sizeof(subset));
40
41 if(s == 0)
42 break;
43 while(s)
44 {
45 cin >> t;
46 maxTo >?= s;
47 maxTo >?= t;
48 map[s][t] = true;
49 map[t][s] = true;
50 cin >> s;
51 }
52
53 dfs(1);
54 if(subset[1])
55 subset[1]--;
56 cout << "Network #" << ++network << endl;
57 bool flag = false;
58 for(int i = 1; i <= maxTo; i++)
59 if(subset[i])
60 {
61 flag = true;
62 cout << " SPF node " << i << ' '
63 << "leaves " << subset[i] + 1 << " subnets" << endl;
64 }
65 if(flag == false)
66 cout << " No SPF nodes" << endl;
67 cin >> s;
68 if(s)
69 cout << endl;
70 }
71
72 return 0;
73 }
74