alan23273850 的刷題筆記
d813: 10583 - Ubiquitous Religions
Tags: disjoint-set
出處：https://zerojudge.tw/ShowProblem?problemid=d813
提交：https://zerojudge.tw/Submissions?problemid=d813&account=allllllan123456
問題：給定 $n\in[1,50000]$ 個人 (1 ~ $n$) 及 $m\in[0,C(n,2)]$ 筆資料指定 a 和 b 屬於同一個團體，最後問你這些人最多形成幾個團體。
解法：讓剛開始的每個人都各自屬於一個獨立團體，並且在實作並查集的過程中每當兩團體合併的時候對團體數量減一，那麼最後的數量就是答案。
1#include <bits/stdc++.h>
2using namespace std;
3
4int p[50001];
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, T=0;
12 while (cin >> n >> m && (n || m)) {
13 for (int i=1; i<=n; i++) p[i] = i;
14 while (m--) { int x, y;
15 cin >> x >> y;
16 x = find(x); y = find(y);
17 if (x != y)
18 n--, p[y] = x;
19 }
20 cout << "Case " << ++T << ": " << n << '\n';
21 }
22 return 0;
23}