暢通工程 Problem Description 某省調查城鎮交通狀況，得到現有城鎮道路統計表，表中列出了每條道路直接連通的城鎮。省政府“暢通工程”的目標是使全省任何兩個城鎮間都可以實現交通（但不一定有直接的道路相連，只要互相間接通過道路可達即可）。問最少還需要建設多少條道路？ Input 測試輸入包含若干測試用例。每個測試用例的第1行給出兩個正整數，分別是城鎮數目N ( < 1000 )和道路數目M；隨後的M行對應M條道路，每行給出一對正整數，分別是該條道路直接連通的兩個城鎮的編號。為簡單起見，城鎮從1到N編號。 注意:兩個城市之間可以有多條道路相通,也就是說 3 3 1 2 1 2 2 1 這種輸入也是合法的 當N為0時，輸入結束，該用例不被處理。 Output 對每個測試用例，在1行裡輸出最少還需要建設的道路數目。 Sample Input 4 2 1 3 4 3 3 3 1 2 1 3 2 3 5 2 1 2 3 5 999 0 0 Sample Output 1 0 2 998 Hint Hint Huge input, scanf is recommended. Source 浙大計算機研究生復試上機考試-2005年 Recommend JGShining 開始的時候的確不知道該如何下手，不過有幸看了杭電ACM的PPT（關於並查集的），裡面有一句話讓我印象深刻，這道題就是赤裸裸的並查集啊！不會做的同學看一下他們的ppt吧！講得的確很好！我分享一下PPT吧！ 有需要的同學好好看看吧！這裡就不多說了！ 我的代碼就是直接套用的！ [cpp] #include<stdio.h> int bin[1002]; int findx(int x) { int r=x; while(bin[r]!=r) r=bin[r]; return r; } void merge(int x,int y) { int fx,fy; fx = findx(x); fy = findx(y); if(fx != fy) bin[fx]=fy; } int main() { int n,m,i,x,y,count; while(scanf("%d",&n),n) { for(i=1;i<=n;i++) bin[i] = i; for(scanf("%d",&m);m>0;m--) { scanf("%d %d",&x,&y); merge(x,y); } for(count=-1, i=1;i<=n;i++) if(bin[i]==i) count++; printf("%d\n",count); } }
