【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d449
【解題想法】並查集，Disjoint Set Union-Find algorithm (DSU)
- 利用一個 array (p) 紀錄每封信件所處類別的根節點。
- 利用一個 unordered_set (st) 紀錄一封信件的同類信件。
- 每次查找 Find() 時，順便進行路徑壓縮。
- 將信件 b 獨立出來時，先判斷其是否為類別的根節點。
- b 是根節點：將其對應的 st[b] 中的第一個節點 c 設為根節點，其他節點合併到「節點c」之下。
- b 不是根節點：找出 b 的根節點 c，將 b 下方的節點合併到 c 之下。
#include <iostream>
#include <unordered_set>
using namespace std;
int p[10005], n, m, a, b, c, ans;
unordered_set <int> st[10005];
int Find(int a){
if (p[a] == a) return a;
else {
st[p[a]].erase(a);
p[a] = Find(p[a]);
st[p[a]].insert(a);
return p[a];
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
while (cin >> n >> m){
for (int i = 1; i <= n; i++){
p[i] = i;
st[i].clear();
}
while (m--){
cin >> a;
if (a == 1){
cin >> b >> c;
b = Find(b);
c = Find(c);
if (c == b) continue;
p[ c] = b;
st[b].insert(c);
}
else{
cin >> b;
if (p[b] == b){
if (st[b].size() == 0) continue;
c = *st[b].begin();
p[ c] = c;
st[b].erase(c);
for (int i:st[b]){
st[ c].insert(i);
p[i] = c;
}
st[b].clear();
}
else{
c = Find(b);
for (int i:st[b]){
st[ c].insert(i);
p[i] = c;
}
st[b].clear();
st[p[b]].erase(b);
p[b] = b;
}
}
}
ans = 0;
for (int i = 1; i <= n; i++){
if (p[i] == i) ans += 1;
}
cout << ans << "\n";
}
}