HDU 1232(併査集)

開通工事
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 8386    Accepted Submission(s): 4181
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.
   
   
   
   
   
   
   
   

    
    
    
     HDU 1272   
   
   
   
   
   
   
   
   

    
    
    
    #include <iostream> using namespace std; #define N 100005 struct set { int parent; //      int rank; //         }elem[N]; int MAX,num; //num        int mark[N]; //       void init() { int i; for(i=0;i<=N;i++) { elem[i].parent=i; elem[i].rank=1; } } int Find(int x) { int root,temp; temp=x; while(x!=elem[x].parent) //      x=elem[x].parent; root=x; x=temp; while (x!=elem[x].parent) //    ，           { temp=elem[x].parent; elem[x].parent=root; x=temp; } return root; } void Union(int a,int b) //       { int x,y; x=Find(a); y=Find(b); if(elem[x].rank>=elem[y].rank) { elem[y].parent=elem[x].parent; elem[x].rank+=elem[y].rank; if(MAX<elem[x].rank) MAX=elem[x].rank; } else { elem[x].parent=elem[y].parent; elem[y].rank+=elem[x].rank; if(MAX<elem[y].rank) MAX=elem[y].rank; } } int main() { int n,m,a,b,x,y; while (scanf("%d",&n),n) { num=0; init(); scanf("%d",&m); while (m--) { scanf("%d%d",&a,&b); x=Find(a); y=Find(b); if(x!=y) Union(a,b); } for(int i=1;i<=n;i++) { if(elem[i].parent==i) num++; } printf("%d/n",num-1); } return 0; }