题解 | #第一题#

//土尔逊Torson 编写于2023/07/04
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define N 1000010
int dad[N], h[N];

using namespace std;

void Initial13301()
{
	for (int i = 0; i < N; i++)
	{
		dad[i] = i;
		h[i] = 0;
	}
}

int Find13301(int x)
{
	if (x != dad[x])
		dad[x] = Find13301(dad[x]);
	return dad[x];
}

void Union13301(int x, int y)
{
	x = Find13301(x);
	y = Find13301(y);
	if (x != y)
	{
		if (h[x] < h[y]) {
			dad[x] = y;
		}
		else if (h[x] > h[y]) {
			dad[y] = x;
		}
		else {
			dad[y] = x;
			h[x]++;
		}
	}
	return;
}

int main() {
	int num = 0, x, y, answer = 0, i;
	Initial13301();
	while (scanf("%d%d", &x, &y) != EOF) {
		num++;
		h[x] = 1, h[y] = 1;
		Union13301(x, y);
	}

	for (i = 0; i < N; ++i) {
		if (h[i] == 0) continue;
		if (Find13301(i) == i) answer++;
	}
	printf("%d\n", answer);
	return EXIT_SUCCESS;
}
// 64 位输出请用 printf("%lld")