hihoCoder #1066：無間道之並查集——幫派臥底識別問題

問題背景

小Hi 和小Ho 誤入青龍幫總部，黑叔叔請求他們協助解決一個棘手問題：幫派中混入許多臥底，調查只能獲得「某人與另一人同陣營」的資訊，無法直接判斷具體陣營。需要一個程序支援兩種操作：

• 合併操作 (op=0)：告知兩人同屬一個陣營。
• 查詢操作 (op=1)：詢問兩人是否同屬一個陣營，根據已知資訊回答 yes 或 no。

核心思路：並查集

這是典型的動態連通性問題。使用並查集維護陣營關係：

1. 將姓名映射為整數索引（用 map）。
2. 每個人初始獨立成集合（父節點指向自己）。
3. 合併：尋找兩人的根節點，將一個根掛到另一個根下。
4. 查詢：判斷兩人的根節點是否相同。
5. 路徑壓縮優化 Find 操作，使時間複雜度趨近 O(α(n))。

關鍵代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;

int father[MAXN];
map<string, int> idx;
int id = 0;

int Find(int x) {
    return x != father[x] ? father[x] = Find(father[x]) : father[x];
}

void Union(int x, int y) {
    int fx = Find(x), fy = Find(y);
    if (fx != fy) father[fx] = fy;
}

int getIdx(const string& name) {
    if (idx.count(name)) return idx[name];
    idx[name] = ++id;
    father[id] = id;
    return id;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        idx.clear();
        id = 0;
        for (int i = 1; i < MAXN; ++i) father[i] = i;

        for (int i = 0; i < n; ++i) {
            int op; string name1, name2;
            cin >> op >> name1 >> name2;
            int u = getIdx(name1), v = getIdx(name2);
            if (op == 0) Union(u, v);
            else cout << (Find(u) == Find(v) ? "yes" : "no") << '\n';
        }
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(N α(N))，N 為操作數（≤ 10^5），α 為反阿克曼函數，極小。
• 空間複雜度：O(N) 存儲父節點陣列與映射表。

樣例解析

輸入 10 次操作，輸出 yes no yes yes，正確識別出同陣營關係。