alan23273850 的刷題筆記
a445: 新手訓練系列- 我的朋友很少
Tags: disjoint-set
出處：https://zerojudge.tw/ShowProblem?problemid=a445
提交：https://zerojudge.tw/Submissions?problemid=a445&account=allllllan123456
問題：給定 $N\in[1,10000]$ 個人 (1 ~ N)，先是 $M\in[1,10000]$ 筆資料說明 a 和 b 屬於同一個團體，接下來才是 $Q\in[1,100000]$ 筆詢問 a 和 b 是否屬於同一個團體。
解法：就典型的並查集，不解釋。
1#include <bits/stdc++.h>
2using namespace std;
3
4int p[10001];
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 a, b, N, M, Q; cin >> N >> M >> Q;
12 while (N--) p[N+1] = N+1;
13 while (M--) cin >> a >> b, a=find(a), b=find(b), p[a]=b;
14 while (Q--) cin >> a >> b, cout << (find(a)==find(b) ? ":)" : ":(") << '\n';
15 return 0;
16}