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

HDU 3234 異或查詢：加權並查集經典應用

編輯：關於C++

問題描述

有 n (≤20000) 個未知整數 X₀…Xₙ₋₁，支援兩類操作（Q ≤ 40000）：

I p v：賦值 Xₚ = v
I p q v：約束 Xₚ ⊕ X_q = v
Q k p₁…pₖ：查詢 Xₚ₁ ⊕ … ⊕ Xₚₖ (k ≤ 15)

若新增事實與已知衝突，輸出衝突信息；查詢無法確定時輸出 "I don't know."。

核心思想：帶權並查集

引入虛擬節點 `n` 代表常數 0。每個節點 `x[i]` 存儲「節點 i 到其根節點的異或值」。

若 `find(p) == find(q)`，則 `x[p] ⊕ x[q]` 為已知值，可直接驗證一致性
合併時：`x[root_p] = x[p] ⊕ x[q] ⊕ v`，保證路徑壓縮後異或關係不變

關鍵數據結構


int pa[maxn];      // 父節點
int val[maxn];     // 到父節點的異或值 (路徑壓縮後為到根的異或值)
int cnt[maxn];     // 查詢時統計各集合出現次數
int n;             // 變量數，虛擬節點索引為 n

核心操作實現

初始化


void init() {
    for (int i = 0; i <= n; ++i) {
        pa[i] = i;
        val[i] = 0;
    }
}

帶路徑壓縮的查找（關鍵：維護異或值）


int find(int x) {
    if (x != pa[x]) {
        int root = find(pa[x]);
        val[x] ^= val[pa[x]]; // 累積到根的異或值
        return pa[x] = root;
    }
    return x;
}

合併操作（返回是否一致）


bool unite(int p, int q, int v) {
    int rp = find(p), rq = find(q);
    if (rp == rq) return (val[p] ^ val[q]) == v;
    // 將 rp 掛到 rq 下
    pa[rp] = rq;
    val[rp] = val[p] ^ val[q] ^ v; // 關鍵公式推導
    return true;
}

查詢處理


// 統計每個集合出現次數
for (int i = 0; i < k; ++i) cnt[find(id[i])] = 0;
for (int i = 0; i < k; ++i) {
    cnt[find(id[i])]++;
    ans ^= val[id[i]];
}
// 判斷是否可確定：每個集合出現次數必為偶數，或包含虛擬節點 n
bool ok = true;
for (int i = 0; i < k; ++i) {
    int r = find(id[i]);
    if (cnt[r] % 2 == 1 && r != n) { ok = false; break; }
}