HDU 1829 蟲子性別判定：帶關係的並查集經典應用

題目背景

教授研究稀有蟲子的性行為，假設只有兩種性別且僅發生異性交互。給定蟲子編號及交互記錄，判斷是否存在同性交互（即假設不成立）。

問題建模

• N 隻蟲子（1 ~ 2000），M 條交互記錄（≤ 1,000,000）
• 每條記錄 (x, y) 表示 x 和 y 發生交互 → 性別不同
• 判斷是否能為所有蟲子分配「雄/雌」兩種性別，使所有記錄滿足異性條件

這是經典的二分圖判定問題，等價於檢測圖中是否存在奇環。

帶關係並查集（擴展域並查集）

為每個蟲子 i 建立兩個節點：

• i：表示「蟲子 i 是雄性」
• i + N：表示「蟲子 i 是雌性」

合並規則：記錄 (x, y) 意味著「x 雄 ⇔ y 雌」且「x 雌 ⇔ y 雄」

unite(x, y + N);  // x 雄與 y 雌同屬一類
unite(x + N, y);  // x 雌與 y 雄同屬一類

衝突檢測：若 find(x) == find(y) 或 find(x+N) == find(y+N)，說明 x 和 y 被強制為同性，但記錄要求異性 → 矛盾，存在同性交互。

完整代碼

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

const int MAXN = 2005 * 2;
int parent[MAXN], rnk[MAXN];

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

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

void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (rnk[x] < rnk[y]) swap(x, y);
    parent[y] = x;
    if (rnk[x] == rnk[y]) ++rnk[x];
}

bool same(int x, int y) {
    return find(x) == find(y);
}

int main() {
    int T, n, m;
    scanf("%d", &T);
    for (int tc = 1; tc <= T; ++tc) {
        scanf("%d%d", &n, &m);
        init(n * 2);
        bool suspicious = false;
        for (int i = 0; i < m; ++i) {
            int x, y;
            scanf("%d%d", &x, &y);
            if (same(x, y) || same(x + n, y + n)) {
                suspicious = true;
            } else {
                unite(x, y + n);
                unite(x + n, y);
            }
        }
        printf("Scenario #%d:\n", tc);
        puts(suspicious ? "Suspicious bugs found!" : "No suspicious bugs found!");
        puts("");
    }
    return 0;
}

關鍵點總結

同類經典題

• POJ 1182 食物鏈（三類關係：捕食、被捕食、同類）
• POJ 1733 帶權並查集（奇偶性關係）
• NOI 2001 炮兵陣地（狀態壓縮 DP + 並查集優化）