浙大大学院生の再試験の機械試験2005--円滑な工事

開通工事
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 22181    Accepted Submission(s): 11553
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年
又一版并查集...

#include <iostream>
using namespace std;
const int MAX=1000;
int parent[MAX+10];
bool root[MAX+10];
int GetParent(int a)
{
	if(parent[a]!=a)
		GetParent(parent[a]);
	else
		return parent[a];
}
void Merge(int a,int b)
{
	int p1=GetParent(a);
	int p2=GetParent(b);
	if(p1==p2)
		return ;
	else
		{
			parent[p2]=p1;
			root[p2]=0;
	}
}
int main()
{
	int n,m;
	while(true)
	{
		scanf("%d",&n);
		if(n==0)
			break;
		scanf("%d",&m);
		for(int i=1;i<=n;i++)
		{
			parent[i]=i;
			root[i]=1;
		}
		while(m--)
		{
			int h,s;
			scanf("%d%d",&h,&s);
			Merge(h,s);
		}
		int sum=0;
		for(int i=1;i<=n;i++)
		{
			if(root[i])
				sum++;
		}
		printf("%d
",sum-1);
	}
	return 0;
}