hdu 畅通工程 [并查集]

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<algorithm>
using namespace std;

const int maxn = 1001;
int father[maxn];

int findfather(int x)
{
	int temp = x;
	while (father[x] != x)
	{
		x = father[x];
	}
	while (father[temp] != temp)
	{
		int z = temp;
		temp = father[temp];
		father[z] = x;
	}
	return x;
}

void _union(int a, int b)
{
	int fa = findfather(a);
	int fb = findfather(b);
	if (fa != fb)
	{
		father[fa] = fb;
	}
}

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

int main()
{
	int x, y, n, m;
	while (cin >> n&&n)
	{
		cin >> m;
		int num = 0;
		init(n);
		while (m--)
		{
			cin >> x >> y;
			_union(x, y);
		}
		for (int i = 1; i <= n; i++)
		{
			if (father[i] == i)
				num++;
		}
		cout << num - 1 << endl;
	}
	return 0;
}