HDOJ 1232:スムーズエンジニアリングとサブマップの個数を調べる

この浙大の大学院生の再試験問題のテーマは大体:1つの図をあげて、少なくともいくつかの辺を追加して図をつなぐことができます.1つの図にN個のサブ図がある場合、明らかにN−1個のエッジを追加すれば、図を連通させることができる.そこでこの問題の授業は1つの図のサブ図の個数を解くことに転化した.
解のサブマップの個数は並べて集めることができて、教材の上の深い検索あるいは広い検索で解くことができて、私は並べて集を調べて解くことを使って、そして集を調べるのは明らかに形式がもっと簡潔であるためです.
私のACコード.
   

#include<iostream>
#include<stdio.h> 
using namespace std;

const int Max = 1000;
int ancestor[Max];
int rank[Max];

int getAncestor(int c)
{	
	while(ancestor[c]) c = ancestor[c];
	
	return c;
}

int main()
{
	int edges, vers;
	int a, b, pa, pb;
	int sum;
	
	while(scanf("%d", &vers) && vers)
	{
		scanf("%d", &edges);
		
		for(int i=1; i<=vers; i++) ancestor[i] = 0, rank[i] = 1;
		
		for(int i=0; i<edges; i++)
		{
			scanf("%d%d", &a, &b);
			
			pa = getAncestor(a);
			pb = getAncestor(b);
			if(pa != pb)
			{
				if(rank[pa] < rank[pb])
				{ 
					ancestor[pa] = pb;
					rank[pb] += rank[pa];
				}
				else
				{
					ancestor[pb] = pa;
					rank[pa] += rank[pb];
				}
			}
		}
		
		sum = 0;
		for(int i=1; i<=vers; i++)
			if(!ancestor[i]) sum ++;
		
		printf("%d
", sum-1);
	}

	system("pause");
	return 0;
}