有n个相互不连通的集合（相互连通的城市归为一个集合），就需要构建n-1条新道路。此题为典型的并查集。用第一种并查集实现。

//2190468 2010-03-16 08:17:26 Accepted 1232 62MS 288K 914 B C++ 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <set>
using namespace std;

const int N = 1004;
int UFSet[N];

int n;//并查集中元素个数
int m;

void init()
{
	for(int i = 1; i <= n; i++)
		UFSet[i] = i;
}

int find(int x)
{//查找x元素所在集合号，时间复杂度为O(1)
	return UFSet[x];
}

void merge(int x, int y)
{//合并元素x和元素y，时间复杂度为O(N)
	int a, b;
	a = min(UFSet[x], UFSet[y]);
	b = max(UFSet[x], UFSet[y]);
	for(int k = 1; k <= n; k++)
		if(UFSet[k] == b)
			UFSet[k] = a;
}

int main()
{
	int i;
	int citya, cityb;
	set<int> S;
	while(scanf("%d", &n) && n)
	{
		scanf("%d", &m);
		init();
		for(i = 0; i < m; i++)
		{
			scanf("%d %d", &citya, &cityb);
			merge(citya, cityb);
		}
		S.clear();
		for(i = 1; i <= n; i++)
			S.insert(find(i));
		printf("%d\n", S.size() - 1);
	}
	return 0;
}

• 相关文章
• 全局相关文章