畅通工程 （C++代码）

解题思路:

                并查集

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
struct Node {
	int x, y;
}s[MAXN];
int N, M;
int f[MAXN];
int getf(int n)
{
	if (f[n] == n)
		return n;
	else
		return getf(f[n]);
}
int main()
{
	while (~scanf("%d", &N) && N)
	{
		scanf("%d", &M);
		for (int i = 1; i <= M; i++)
			scanf("%d%d", &s[i].x, &s[i].y);
		for (int i = 1; i <= N; i++)
			f[i] = i;
		int ans = N-1;
		for (int i = 1; i <= M; i++)
		{
			int fx = getf(s[i].x), fy = getf(s[i].y);
			if (fx != fy)
			{
				f[fx] = fy;
				ans--;
			}
		}
		cout << ans << endl;
	}
	return 0;
}