HDU 1232(暢通工程)題解，hdu暢通工程

HDU 1232(暢通工程)題解，hdu暢通工程

以防萬一，題目原文和鏈接均附在文末。那麼先是題目分析：

【一句話題意】

給定一具有N個節點的圖和其邊集，求其集合數量。

【題目分析】

並查集經典題...其實就是創建好並查集就行了..

【算法流程】

於是這裡就是放並查集的基本內容的..
用一個數組的下標來對應節點，值來對應其父節點，並查集英文是Disjoint Sets，就叫DJSet好了XD

1 int getDjSetPar(int id) { //取得某節點的父節點
2     if (dj[id]==id) return id;
3     else return getDjSetPar(dj[id]);
4 }
5 
6 void mergeDjSet(int id1,int id2) { //連接兩個集合到一起
7     dj[getDjSetPar(id1)] = getDjSetPar(id2);
8 }

還有一個這題沒用到

void Query(int a,int b) {//判斷 a 和 b 是否在同一個集合
   return GetPar(a) == GetPar(b);
}

就是這些了...

 1 //Disjoint Sets
 2 
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <iostream>
 6 
 7 using namespace std;
 8 
 9 int dj[1061];
10 
11 int getDjSetPar(int id) { 
12     if (dj[id]==id) return id;
13     else return getDjSetPar(dj[id]);
14 }
15 
16 void mergeDjSet(int id1,int id2) {
17     dj[getDjSetPar(id1)] = getDjSetPar(id2);
18 }
19 
20 int main() {
21     int N, M, id1, id2;
22     while(~scanf("%d",&N)){
23         if (N==0) break;
24         else scanf("%d",&M);
25         for(int i = 1;i<=N;i++) {
26             dj[i] = i;
27         }
28         while(M--) {
29             scanf("%d%d",&id1,&id2);
30             if (id1 != getDjSetPar(id2)) mergeDjSet(id1,id2);
31         }
32         int counter = 0;
33         for(int i = 1;i<=N;i++) {
34             if (getDjSetPar(i) == i) counter++;
35         }
36         printf("%d\n",counter-1);
37     }
38 } 
39 
40 /*
41 In 
42 4 2
43 1 3
44 4 3
45 3 3
46 1 2
47 1 3
48 2 3
49 5 2
50 1 2
51 3 5
52 999 0
53 0
54 
55 Out
56 1
57 0
58 2
59 998
60 */

題目鏈接：暢通工程（HDU 1232）

題目屬性：並查集

相關題目：1198 1213 1272

題目原文：
【Desc】某省調查城鎮交通狀況，得到現有城鎮道路統計表，表中列出了每條道路直接連通的城鎮。省政府“暢通工程”的目標是使全省任何兩個城鎮間都可以實現交通（但不一定有直接的道路相連，只要互相間接通過道路可達即可）。問最少還需要建設多少條道路？
【In】測試輸入包含若干測試用例。每個測試用例的第1行給出兩個正整數，分別是城鎮數目N ( < 1000 )和道路數目M；隨後的M行對應M條道路，每行給出一對正整數，分別是該條道路直接連通的兩個城鎮的編號。為簡單起見，城鎮從1到N編號。
注意:兩個城市之間可以有多條道路相通,也就是說
3 3
1 2
1 2
2 1
這種輸入也是合法的
當N為0時，輸入結束，該用例不被處理。
【Out】對每個測試用例，在1行裡輸出最少還需要建設的道路數目。
【SampIn/Out】參見代碼下方的注釋。