f677: FJCU_109_Winter_Day3_Lab1 並查集練習

解題心得

為了方便直接看 num[0] 就知道是答案， union 的時候要讓 index 大的指到小的。

程式碼

#include <iostream>
using namespace std;

int p[1000] = { 0 }, num[1000] = { 0 };
int find_set(int u)
{
	if (p[u] == u) return u;
	return p[u] = find_set(p[u]);
}
int main()
{
	int n, m, a, b;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		p[i] = i, num[i] = 1;
	while (m--)
	{
		cin >> a >> b;
		a = find_set(a), b = find_set(b);
		if (a != b)
		{
			if (b > a)
				swap(a, b);
			p[a] = b; // a 指到 b
			num[b] += num[a];
		}
	}
	cout << num[0] << endl;
	return 0;
}