【題解】ZeroJudge d449: 垃圾信件

【題目敘述】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";
    }
}
分享本文 Share with friends