圖論練習題 備用交換機 gd 題解

問題描述

n個城市之間有通訊網絡，每個城市都有通訊交換機，直接或間接與其它城市連接。因電子設備容易損壞，需給通訊點配備備用交換機。但備用交換機數量有限，不能全部配備，只能給部分重要城市配置。於是規定：如果某個城市由於交換機損壞，不僅本城市通訊中斷，還造成其它城市通訊中斷，則配備備用交換機。請你根據城市線路情況，計算需配備備用交換機的城市個數，及需配備備用交換機城市的編號。

【輸入格式】

輸入文件有若干行

第一行，一個整數n，表示共有n個城市(2<=n<=100)

下面有若干行,每行2個數a、b，a、b是城市編號，表示a與b之間有直接通訊線路。

【輸出格式】

輸出文件有若干行

第一行，1個整數m，表示需m個備用交換機，下面有m行，每行有一個整數，表示需配備交換機的城市編號，輸出順序按編號由小到大。如果沒有城市需配備備用交換機則輸出0。

 

【輸入輸出樣例】

輸入文件名： gd.in

7

1 2

2 3

2 4

3 4

4 5

4 6

4 7

5 6

6 7

輸出文件名：gd.out

2

2

4

【分析】

裸求割頂。DFS。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25685

01 /*
02 *Problem: 備用交換機
03 *Author: Yee-fan Zhu
04 *GTalk: zyfworks@gmail.com
05 */
06 #include <cstdlib>
07 #include <cstdio>
08 #include <set>
09 #include <vector>
10 #include <algorithm>
11 using namespace std;
12 const int MAXN=101;
13 typedef vector<int> Vec;
14 int N;
15 Vec Map[MAXN];
16 int Ancestor[MAXN];
17 int Deep[MAXN];
18 int Parent[MAXN];
19 int total=0;
20 void init()
21 {
22     scanf("%d\n",&N);
23     int a,b;
24     while(scanf("%d %d\n",&a,&b)==2)
25     {
26         Map[a].push_back(b);
27         Map[b].push_back(a);
28     }
29 }
30
31 int Min(int a,int b)
32 {
33     return a<b?a:b;
34 }
35
36 void dfs(int now,int pnt)
37 {
38     int tot=0;
39     Parent[now]=pnt;
40     Deep[now]=Ancestor[now]=++total;
41     int nxt;
42     for(unsigned int i=0;i<Map[now].size();i++)
43     {
44         nxt=Map[now][i];
45         if(Deep[nxt]==0)
46         {
47             tot++;
48             dfs(nxt,now);
49             Ancestor[now]=Min(Ancestor[now],Ancestor[nxt]);
50         }
51         else
52         {
53             if(nxt!=pnt)
54             {
55                 Ancestor[now]=Min(Ancestor[now],Deep[nxt]);
56             }
57         }
58     }
59 }
60
61 int main()
62 {
63     freopen("gd.in","r",stdin);
64     freopen("gd.out","w",stdout);
65     init();
66     /*
67     * 将刘汝佳黑书上的Root节点设为1号节点
68     *详见《算法艺术与信息学竞赛》第285页
69     */
70     dfs(1,0);
71     int tmp;
72     set<int> Res;
73     int Tmp=0;
74     for(int i=2;i<=N;i++)
75     {
76         tmp=Parent[i];
77         if(tmp==1)
78             Tmp++; 
79         else if(Ancestor[i]>=Deep[tmp] && tmp!=0)
80             Res.insert(tmp);
81     }
82     if(Tmp>1)
83     {
84         /*
85         *当根有数量>1的儿子时，根是图的割顶
86         *详见 《算法艺术与信息学竞赛》第286页
87         */
88         Res.insert(1);
89     }
90     printf("%d\n",Res.size());
91     for(set<int>::iterator iter=Res.begin();iter!=Res.end();iter++)
92         printf("%d\n",*iter);
93     return 0;
94 }