您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 3234 / UVA 12232 / LA 4487 Exclusive：帶權並查集解決 XOR 方程組

編輯：關於C++

這是一道經典的「帶權並查集」題目，核心思想是利用並查集維護變量之間的 XOR 關係，並在合併過程中動態更新權值，從而判斷事實是否衝突、查詢是否可推導。題目編號雖多（HDU 3234、UVA 12232、LA 4487），但本質相同：給定 n 個未知變量 X₀…Xₙ₋₁（值 < 2²⁰），逐條給出事實（賦值或 XOR 關係）與查詢，要求即時回答或檢測衝突。

一、題目重述

變量：n 個非負整數 X₀, X₁, …, Xₙ₋₁，值不變但初始未知。
事實類型：
- I P V：Xₚ = V
- I P Q V：Xₚ ⊕ X_Q = V
查詢類型：Q K P₁ P₂ … Pₖ：詢問 Xₚ₁ ⊕ Xₚ₂ ⊕ … ⊕ Xₚₖ 的值。
輸出規則：
- 查詢無法從已知事實推導 → I don't know.
- 第 i 條事實與前序事實衝突 → The first i facts are conflicting. 並停止後續處理。

二、核心模型：帶權並查集

將每個變量視為節點，額外引入一個虛擬節點 n 代表常數 0（因 a ⊕ 0 = a），即可將「賦值」轉化為「與虛擬節點的 XOR 關係」。

數據結構定義

const int MAXN = 20005;  // n ≤ 20000，加上虛擬節點
int fa[MAXN];            // 父節點
int val[MAXN];           // val[x] = x ⊕ fa[x] （到父節點的 XOR 值）

路徑壓縮與權值更新

int find(int x) {
    if (x != fa[x]) {
        int f = fa[x];
        fa[x] = find(fa[x]);      // 遞歸找根
        val[x] ^= val[f];         // 關鍵：x⊕新父 = (x⊕舊父) ⊕ (舊父⊕新父)
    }
    return fa[x];
}

經過 find(x) 後，fa[x] 直接指向根節點，val[x] 即為 x ⊕ root。

合併操作

已知 a ⊕ b = c，設 fa = find(a), fb = find(b)。
若 fa == fb，檢查 (val[a] ^ val[b]) == c，否則衝突。
若不同根，令 fa 掛在 fb 下，需設定 val[fa] = val[a] ^ val[b] ^ c。
證明：
val[fa] = fa ⊕ fb
val[a] = a ⊕ fa → fa = a ⊕ val[a]
val[b] = b ⊕ fb → fb = b ⊕ val[b]
代入：val[fa] = (a ⊕ val[a]) ⊕ (b ⊕ val[b]) = val[a] ⊕ val[b] ⊕ (a ⊕ b) = val[a] ⊕ val[b] ⊕ c。
優化：為保證樹高，合併時總將非虛擬根掛在虛擬根（或秩較大者）下。

三、查詢處理

查詢 Xₚ₁ ⊕ … ⊕ Xₚₖ：

對每個 Pᵢ 呼叫 find(Pᵢ)，得到根 rᵢ 及 val[Pᵢ] = Pᵢ ⊕ rᵢ。
若所有 rᵢ 均為虛擬節點 n，結果確定，直接 XOR 所有 val[Pᵢ]。
否則統計每個非虛擬根出現的次數。若某根出現奇數次，該根的值無法消去，答案不確定 → I don't know.；若全部偶數次，根值相互抵消，答案確定。

四、完整參考代碼（C++11）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20005;
int n, Q;
int fa[MAXN], val[MAXN];
int fact_cnt;                 // 已處理事實計數
bool conflict = false;

int find(int x) {
    if (x != fa[x]) {
        int f = fa[x];
        fa[x] = find(fa[x]);
        val[x] ^= val[f];
    }
    return fa[x];
}

// 返回 true 表示合併成功/一致，false 表示衝突
bool unite(int a, int b, int c) {
    int fa = find(a), fb = find(b);
    if (fa == fb) return (val[a] ^ val[b]) == c;
    // 讓虛擬節點 n 盡量做根
    if (fa == n) swap(fa, fb);
    fa[fa] = fb;
    val[fa] = val[a] ^ val[b] ^ c;
    return true;
}

int query(const vector<int>& nodes) {
    unordered_map<int, int> cnt;
    int ans = 0;
    for (int x : nodes) {
        int r = find(x);
        ans ^= val[x];
        if (r != n) cnt[r]++;
    }
    for (auto& [r, c] : cnt) if (c & 1) return -1; // 不確定
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc = 0;
    while (cin >> n >> Q, n || Q) {
        cout << "Case " << ++tc << ":\n";
        // 初始化：0~n-1 為變量，n 為虛擬節點（值恆為 0）
        for (int i = 0; i <= n; ++i) fa[i] = i, val[i] = 0;
        fact_cnt = 0;
        conflict = false;
        
        string op;
        for (int q = 0; q < Q; ++q) {
            cin >> op;
            if (conflict) continue; // 衝突後忽略所有輸入
            
            if (op == "I") {
                int p, v, q2 = -1;
                cin >> p;
                // 嘗試讀取第四個數，區分 I P V 和 I P Q V
                // 這裡簡化：實際需按行讀取或用 peek 判斷
                // 完整解析略，核心邏輯如下：
                // 若只有 p v：unite(p, n, v)
                // 若有 p q v：unite(p, q, v)
                ++fact_cnt;
                if (!unite(/* 參數 */)) {
                    cout << "The first " << fact_cnt << " facts are conflicting.\n";
                    conflict = true;
                }
            } else { // Q
                int k; cin >> k;
                vector<int> nodes(k);
                for (int i = 0; i < k; ++i) cin >> nodes[i];
                int res = query(nodes);
                if (res == -1) cout << "I don't know.\n";
                else cout << res << '\n';
            }
        }
        cout << '\n';
    }
    return 0;
}