题解

并查集

#include <iostream>
#include <cstdio>
using namespace std;
int father[100005];
int find(int n){
	if(father[n] != n) father[n] = find(father[n]);
	return father[n];
}
bool merge(int x, int y){
	int n = find(x), m = find(y);
	if(n == m) return 0;//已经在一起了
	father[n] = m;
	return 1;//合并成功
}
int main(){
	int n, m;
	while(cin >> n >> m){
        if(n == 0) return 0;
		for(int i = 1; i <= n; i++){
			father[i] = i;
		}
		int ct = n;
		for(int i = 1; i <= m; i++){
			int x, y;
			cin >> x >> y;
			ct -= merge(x, y);
		}
		cout << ct - 1 << endl;
	}
}