HDU 1829 A Bug's Life：帶關係的並查集 (性別判斷)

題目大意

n 隻蟲子，m 對交互記錄 (a,b) 表示 a 和 b 異性交互。判斷是否存在矛盾（即某對同性交互）。蟲子編號 1~n，n≤2000, m≤1e6。

核心模型：帶敵對關係的並查集

維護兩類關係：

• 同類關係： 並查集 `fa[x]` 表示 x 所在集合代表元（同性群）。
• 異類關係： `sex[x]` 記錄 x 的異性群代表元（任意一個異性）。

處理邏輯

對每對 (a,b)：

1. 若 `find(a) == find(b)` → 矛盾（同性交互）。
2. 否則建立異性關係：
   • 若 `sex[a] == 0`，設 `sex[a] = b` (a 的異性群代表為 b)；否則 `union(sex[a], b)` (將 b 併入 a 的異性群)。
   • 對 b 同理：`sex[b] == 0 ? sex[b]=a : union(sex[b], a)`。

代碼實現 (C++)

#include 
#include 
const int MAXN = 2005;

int fa[MAXN], sex[MAXN];

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

void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x != y) fa[x] = y;
}

int main() {
    int T; scanf("%d", &T);
    for (int tc = 1; tc <= T; tc++) {
        int n, m; scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) { fa[i] = i; sex[i] = 0; }
        bool suspicious = false;
        for (int i = 0; i < m; i++) {
            int a, b; scanf("%d%d", &a, &b);
            if (suspicious) continue;
            int fa_a = find(a), fa_b = find(b);
            if (fa_a == fa_b) { suspicious = true; continue; }
            if (sex[a] == 0) sex[a] = b; else unite(sex[a], b);
            if (sex[b] == 0) sex[b] = a; else unite(sex[b], a);
        }
        printf("Scenario #%d:\n", tc);
        puts(suspicious ? "Suspicious bugs found!" : "No suspicious bugs found!");
        if (tc != T) printf("\n"); // 題目要求場景間空行
    }
    return 0;
}

關鍵點

• `sex[x]` 存儲的是「x 的異性群的代表元」，而非具體某個異性個體。
• 合併時 `unite(sex[a], b)` 將 b 併入 a 的異性群，保證異性群內部同性。
• 大輸入量 (m≤1e6) 必須用 `scanf`/`printf`，並開啟 O2 優化。
• 輸出格式嚴格：每個場景後空行，最後一個場景後無空行 (或有也接受，視 OJ)。