POJ 2492 A Bug's Life：帶關係的並查集判斷二分圖

問題描述

n隻蟲子，m對交互記錄。蟲子分雌雄兩群，交互只發生在異性之間。判斷記錄是否自洽（即圖是否為二分圖）。輸出"Suspicious bugs found!"或"No suspicious bugs found!"。

並查集擴展：維護關係

傳統並查集只維護連通性。本題需維護「同性/異性」關係。
引入mark[x]：x到根節點的關係 parity（0=同性，1=異性）。

關鍵操作

查找（路徑壓縮+關係更新）

int getFather(int x) {
    if(x == f[x]) return x;
    int t = f[x];
    f[x] = getFather(f[x]);
    mark[x] = (mark[x] + mark[t]) % 2; // 關係疊加：同+同=同，同+異=異...
    return f[x];
}

合併（關係約束）

void make(int a, int b) { // a,b為異性
    int t1 = getFather(a), t2 = getFather(b);
    if(t1 != t2) {
        f[t1] = t2;
        // 要求：a,b異性 → mark[a] + mark[b] + mark[t1] ≡ 1 (mod 2)
        // 即 mark[t1] = (1 - mark[a] - mark[b]) mod 2
        // 簡化：若mark[a]==mark[b]則需設置mark[t1]=1，否則0
        if((mark[a] + mark[b]) % 2 == 0) mark[t1] = 1;
    } else {
        // 同一集合，檢查一致性
        if(mark[a] == mark[b]) flag = false; // 矛盾：本應異性卻同性
    }
}

原理圖解

初始：每蟲自成集合，mark=0（與自己同性）

合併(1,2)：
  1根=1, mark[1]=0；2根=2, mark[2]=0
  要求1,2異性 → mark[1]+mark[2]+mark[新根關係] ≡ 1
  → 0+0+mark[1→2] ≡ 1 → mark[1]=1（1與新根2異性）

合併(2,3)：
  2根=2, mark[2]=0；3根=3, mark[3]=0
  要求2,3異性 → mark[2]=1（同理）

查詢(1,3)：
  find(1)：路徑1→2，mark[1]=(1+0)%2=1（1與根2異性）
  find(3)：mark[3]=1（3與根2異性）
  mark[1]==mark[3] → 1,3同性 → 合法（無矛盾）

完整流程

1. 初始化：`f[i]=i, mark[i]=0, flag=true`
2. 讀入每對交互，調用`make(x,y)`
3. 若任意`make`導致`flag=false`，輸出可疑
4. 否則輸出無可疑

複雜度

時間：近似O(m α(n))，α為反阿克曼函數
空間：O(n)
n≤2000，m未給上限但極快。