1953 ProblemB円滑化工事

問題B:円滑工事
時間制限:1 Secメモリ制限:32 MBコミット:109解決:63
タイトルの説明
ある省は都市交通状況を調査し、既存の都市道路統計表を得て、各道路が直接つながっている都市をリストした.省政府の「円滑な工事」の目標は、全省のどの2つの都市間でも交通を実現させることである(ただし、直接的な道路がつながっているとは限らず、互いに間接的に道路を通過すればよい).少なくとも何本の道路を建設する必要があるかを聞く.
入力
テスト入力には、いくつかのテスト例が含まれます.各試験例の第1行は、都市数N(<1000)と道路数Mの2つの正の整数を与える.その後のM行はM道に対応し、各行は正の整数のペアを与え、それぞれこの道が直接つながっている2つの町の番号である.簡単にするために、町は1からN番までです.注意:2つの都市の間には複数の道路が通じることができ、すなわち3 3 3 1 2 2 1という入力も合法的であり、Nが0の場合、入力が終了し、この例は処理されない.
しゅつりょく
各試験例に対して,1行で最低でも建設が必要な道路数を出力する.
サンプル入力

5 3
1 2
3 2
4 5
0

サンプル出力

1

経験の総括
古典的な並列調査アルゴリズムは,最後に集合の数Nを統計し,建設する必要がある道路数をN−1とすることができる.
正しいコード

#include 

int father[1010];

int findFather(int a)
{
	int x=a;
	while(x!=father[x])
	{
		x=father[x];
	}
	while(a!=father[a])
	{
		int z=a;
		a=father[a];
		father[z]=x;
	}
	return x;
}
void Union(int a, int b)
{
	int A=findFather(a);
	int B=findFather(b);
	if(A!=B)
	{
		father[A]=B;
	}
}
void init(int n)
{
	for(int i=1;i<=n;++i)
	{
		father[i]=i;
	}
}
int main()
{
	int n,k,dot1,dot2;
    while(~scanf("%d",&n))
    {
    	if(n==0)
    		break;
    	scanf("%d",&k);
    	init(n);
    	for(int i=0;i