hdu 1232:スムーズエンジニアリング(データ構造、ツリー、およびコレクション)

開通工事
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 25388    Accepted Submission(s): 13241
Problem Description
ある省は都市交通状況を調査し、既存の都市道路統計表を得て、各道路が直接つながっている都市をリストした.省政府の「円滑な工事」の目標は、全省のどの2つの都市間でも交通を実現させることである(ただし、直接的な道路がつながっているとは限らず、互いに間接的に道路を通過すればよい).最低でも何本の道路を建設する必要がありますか? 
 
Input
テスト入力には、いくつかのテスト例が含まれます.各試験例の第1行は、都市数N(<1000)と道路数Mの2つの正の整数を与える.その後のM行はM道に対応し、各行は正の整数のペアを与え、それぞれこの道が直接つながっている2つの町の番号である.簡単にするために、町は1からN番までです. 
注意:2つの都市の間には複数の道路が通じ合うことができます.つまり、
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   |   We have carefully selected several similar problems for you:  
1233  
1272  
1875  
1879  
1213  
 
データ構造:ツリー実装、古典的な問題を調べます.
前に書いて調べた問題ですが、今回は前回書いたテンプレートをそのまま使用しました.
Nの都市があることを意味して、Mの道路、以下はMの道路の具体的な両端が連通する都市を提供して、またどれだけの道路を修理してすべての都市を連通することができますかを求めます.
構想:道路がつながっている都市が1つの集合を計算し、すべての都市が全部で何個あるかを調べて、この集合数-1で修理する必要がある道路数です.
タイトルコード:
 

 1 #include <iostream>

 2 using namespace std;  3 /*        4 */

 5 int UFS_NUM;    //        

 6 typedef struct node{  7     int data;    //        

 8     int rank;    //      

 9     int parent;    //          

10 }UFSTree;        //          

11 void MAKE_SET(UFSTree t[])    //        

12 { 13     int i; 14     for(i=1;i<=UFS_NUM;i++){ 15         t[i].data = i;        //        

16         t[i].rank = 0;        //     0 

17         t[i].parent = i;    //           

18  } 19 } 20 int FIND_SET(UFSTree t[],int x)    // x            

21 { 22     if(t[x].parent == x)    //      

23         return x;    //     ，   x 

24     else    //       

25         return FIND_SET(t,t[x].parent);    //        x 

26 } 27 void UNION(UFSTree t[],int x,int y)    // x y       

28 { 29     x = FIND_SET(t,x);    //   x            

30     y = FIND_SET(t,y);    //   y            

31     if(t[x].rank > t[y].rank)    //y        x     

32         t[y].parent = x;        //  y     x    ，x    y       

33     else{                //y          x      

34         t[x].parent = y;            //  x     y    ，y    x       

35         if(t[x].rank==t[y].rank)    //x   y         

36             t[y].rank++;            //y       1 

37  } 38 } 39 int main() 40 { 41     int N,M; 42     UFS_NUM=1000; 43     UFSTree u[1001]; 44     while(cin>>N){ 45         if(N==0) break; 46         cin>>M; 47  MAKE_SET(u); 48         for(int i=1;i<=M;i++){ 49             int x,y; 50             cin>>x>>y; 51  UNION(u,x,y); 52  } 53         int count = 0; 54         for(int i=1;i<=N;i++) 55             if(FIND_SET(u,i)==i) 56                 count++; 57         cout<<count-1<<endl; 58  } 59     return 0; 60 }

 
Freecode : www.cnblogs.com/yym2013