题解 | #第一题#

并查集的简单板子 属实没想到要申请1百万个
#include<iostream>
using namespace std;
#define N 1000010

int father[N];
bool visit[N];

int Find(int x) {
	if (father[x] != x) {
		father[x] = Find(father[x]);
	}
	return father[x];
}

void Union(int x, int y,int & num) {
	x = Find(x);
	y = Find(y);
	if (x != y) {
		num++;
		father[y] = x;  //直接相连
	}

}


int main() {
	int n, m;
	for (int i = 0; i < N; i++) {  //并查集初始化
		father[i] = i;
		visit[i] = false;
	}
	int num = 0;  //记录已经连接节点的个数

	while (cin >> n >> m) {
		visit[n] = true;
		visit[m] = true;
		Union(n, m, num);

	}
	int count = 0;
	for (int i = 0; i < N; i++) {
		if (visit[i] == true) {
			count++;
		}
	}
	cout << count - num << endl;
}