d831: 畢業旅行

解題心得

額外開一個陣列來記錄該 set 的數量，要找 root(老大) 才是最新的數量。

程式碼

#include <iostream>
using namespace std;

int n, p[1000000] = { 0 }, num[1000000] = { 0 };

int find_set(int v)
{
	if (p[v] == v) return v;
	return p[v] = find_set(p[v]);
}
void init()
{
	for (int i = 0; i < 1000000; i++)
		p[i] = i, num[i] = 1;
}

int main()
{
	int m, a, b;
	while (cin >> n >> m)
	{
		int ans = 1;
		init();
		while (m--)
		{
			cin >> a >> b;
			a = find_set(a), b = find_set(b);
			if (a != b)
			{
				num[b] += num[a];
				p[a] = b; // a 指向 b
				ans = max(ans, num[b]);
			}
		}
		cout << ans << endl;
	}

	return 0;
}