HDU 1829 A Bug's Life：並查集檢測同性關係

題目

蟲子有雌雄之分，互動只發生在異性之間。給定 n 隻蟲子和 m 次互動 (x,y 表示互動)，判斷是否存在矛盾（即同性互動）。輸出 "Suspicious bugs found!" 或 "No suspicious bugs found!"。

並查集擴展域

為每隻蟲子建立兩個節點：x 代表雄性，x+n 代表雌性。互動 (x,y) 意味著 x 和 y 性別不同 → 合併 x 與 y+n，y 與 x+n。若發現 x 和 y 已在同一集合 → 矛盾。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000;
int pre[2*MAXN+5];
bool ok;

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

void unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) { ok = false; return; }
    pre[fx] = fy;
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        int n, m; scanf("%d%d", &n, &m);
        for (int i = 1; i <= 2*n; i++) pre[i] = i;
        ok = true;
        for (int i = 0; i < m; i++) {
            int x, y; scanf("%d%d", &x, &y);
            if (ok) {
                unite(x, y+n);
                unite(y, x+n);
            }
        }
        printf("Scenario #%d:\n", cas);
        puts(ok ? "No suspicious bugs found!" : "Suspicious bugs found!");
        puts("");
    }
    return 0;
}