superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

ZOJ 1119 - SPF

Posted on 2008-04-09 09:32 superman 阅读(304) 评论(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, falsesizeof(map));
37         memset(low, 0sizeof(low));
38         memset(visited, 0sizeof(visited));
39         memset(subset, 0sizeof(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 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理