alan23273850 的刷題筆記
d831: 畢業旅行
Tags: disjoint-set
出處：https://zerojudge.tw/ShowProblem?problemid=d831
提交：https://zerojudge.tw/Submissions?problemid=d831&account=allllllan123456
問題：給定 $n\in[1,1000000]$ 個元素 (0 ~ n-1)，接著有 $m\in[1,100000]$ 筆資料說明 a 和 b 屬於同一個集合。請問最大的集合大小 (它所擁有的元素數量)。
解法：這題也是典型的並查集，只是需要一個額外的陣列去記錄每個集合的大小而已。
1#include <bits/stdc++.h>
2using namespace std;
3
4int p[1000000], s[1000000];
5
6int find(int x) {
7 return x == p[x] ? x : p[x] = find(p[x]);
8}
9
10int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
11 int n, m, a, b;
12 while (cin >> n >> m) {
13 for (int i=0; i<n; i++) p[i]=i, s[i]=1;
14 while (m--) { cin >> a >> b;
15 a = find(a); b = find(b);
16 if (a != b) // 注意到當 a 和 b 本就屬於同一個團體時，統計數量不能再做更動，這個陷阱佔 60% 的分數。
17 p[a] = b, s[b] += s[a];
18 }
19 cout << *max_element(s, s+n) << '\n';
20 }
21 return 0;
22}