学步园

    这道浙大的研究生上机复试题题意大致是：给一个图，问最少添加几条边可以使图联通。如果一个图有N个子图，显然添加N-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\n", sum-1);
	}

	system("pause");
	return 0;
}