POJ 2492 A Bug's Life：並查集判斷二分圖（蟲子性別衝突）

題目大意

n 隻蟲子，m 對異性交互記錄。判斷記錄中是否存在矛盾（同性交互）。多測試用例。

並查集 + 異性標記

• fa[x] 並查集父節點。
• opp[x]：與 x 異性的某個蟲子（代表元）。
• 處理記錄 (a,b)：
  1. 若 a,b 都無標記：opp[a]=b, opp[b]=a。
  2. 若 a 有標記 opp[a]：b 與 opp[a] 同性 → union(b, opp[a])。
  3. 若 b 有標記 opp[b]：a 與 opp[b] 同性 → union(a, opp[b])。
  4. 若都有標記：union(opp[a], b) 且 union(opp[b], a)。
• 每次處理後檢查 find(a)==find(b) → 矛盾。

代碼

#include <cstdio>
#include <iostream>
using namespace std;
int opp[2005], fa[2005];
int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); }
void unite(int a,int b) { int x=find(a),y=find(b); if(x!=y) fa[x]=y; }
int main() {
    int T; cin>>T;
    for(int tc=1; tc<=T; tc++) {
        bool sus=false; int n,m; cin>>n>>m;
        for(int i=1;i<=n;i++) fa[i]=i, opp[i]=0;
        while(m--) {
            int a,b; cin>>a>>b;
            if(!opp[a] && !opp[b]) { opp[a]=b; opp[b]=a; }
            else if(!opp[a] && opp[b]) { opp[a]=b; unite(a, opp[b]); }
            else if(opp[a] && !opp[b]) { opp[b]=a; unite(b, opp[a]); }
            else { unite(opp[a], b); unite(opp[b], a); }
            if(find(a)==find(b)) sus=true;
        }
        printf("Scenario #%d:\n", tc);
        puts(sus ? "Suspicious bugs found!" : "No suspicious bugs found!");
        puts("");
    }
    return 0;
}

本質

判斷圖是否為二分圖。並查集維護「同性」等價類，opp 記錄異性代表。經典技巧。