HDU 1829 A Bug's Life：帶性別關係的並查集（二分圖檢測）

問題轉化

蟲子雙性，給定 n 隻蟲子、m 對交互關係。判斷是否存在同性交互（即圖中是否有奇環）。等價於：動態維護二分圖性質。

並查集擴展：異性關係數組

• fa[x]：並查集父節點。
• opp[x]：x 所在集合的「異性代表」（即與 x 同集合的所有蟲子，異性集合的代表元）。

合併邏輯 Union(x, y)

x、y 為異性（交互關係）。

1. 找根 fx = find(x), fy = find(y)。
2. 若 fx == fy → 同集合卻要求異性 → 矛盾（存在同性交互）。
3. 否則合併：
   fa[fx] = fy（或按秩合併）。
   關鍵：將 fx 的異性代表 opp[fx] 與 fy 合併，fy 的異性代表 opp[fy] 與 fx 合併。
   更新 opp[fx] = fy, opp[fy] = fx。

代碼實現

int fa[MAXN], opp[MAXN];
bool flag;

int find(int x) { return x==fa[x] ? x : fa[x]=find(fa[x]); }

void Union(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) { flag = false; return; }
    if (opp[fx]) fa[opp[fx]] = fy; // fx的異性併入fy
    if (opp[fy]) fa[opp[fy]] = fx; // fy的異性併入fx
    opp[fx] = fy; opp[fy] = fx;    // 建立新異性關係
}

正確性解析

維持不變量：同一並查集內的所有節點同性，opp[根] 指向的集合為其異性集合。合併時將兩性關係正確傳遞，若發現需合併同性集合則報衝突。

複雜度

近似 O(α(n)) 每操作，極快。