05 复试 畅通工程

给出m个城镇，n条路，问还需修几条路才能连通所有城镇。

基本并查集问题

#include<iostream>
using namespace std;
#include<memory.h>
int city[1001];

int find(int pos)
{
	if(city[pos]==-1)
		return pos;
	return city[pos]=find(city[pos]);
}


int merge(int a,int b)
{
	int roota=find(a);
	int rootb=find(b);
	if(roota==rootb)
		return 0;
	city[roota]=rootb;
	return 1;
}


int main()
{
	int n,m;
	int s,e;
	int count;
	while(1)
	{
		cin>>n;
		memset(city,-1,sizeof(city));
		if(n==0)
			break;
		cin>>m;
		while(m--)
		{
			cin>>s;
			cin>>e;
			merge(s,e);
		}
		
		count = 0;
		for(int i=1;i<=n;i++)
		{
			if(city[i]==-1)
				count++;
		}
		cout<<count-1<<endl;
	}
}