CSU 1356 Catch：奇環檢測與二分圖染色

問題描述

給定無向圖（n 點 m 邊，無重邊自環），從任意點出發，每秒移動到相鄰點（可走重複邊，不可原地停留）。問是否存在某時刻 t，使得所有 n 個點都可能被到達。等價於：圖是否連通且存在奇環。

數學轉換

• 偶數步到達的點集與奇數步到達的點集形成二分圖染色。
• 若圖為二分圖（無奇環），則奇/偶步到達的點集固定，永無法同時覆蓋所有點 → NO。
• 若存在奇環，繞行奇環可翻轉奇偶性，使任意點既可在奇步也可在偶步到達 → YES（前提連通）。

三種檢測奇環方法

1. DFS 二分圖染色

int color[MAXN]; // -1 未訪問，0/1 兩色
bool hasOddCycle = false;

bool dfs(int u, int c) {
    color[u] = c;
    for (int v : adj[u]) {
        if (color[v] == -1) {
            if (!dfs(v, c^1)) return false;
        } else if (color[v] == c) {
            hasOddCycle = true;
            return false;
        }
    }
    return true;
}

2. BFS 染色（非遞歸，避免棧溢出）

queue q;
color[s] = 0; q.push(s);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (color[v] == -1) { color[v] = color[u]^1; q.push(v); }
        else if (color[v] == color[u]) { hasOddCycle = true; break; }
    }
}

3. 加權並查集（關係型並查集）

維護 val[x] 表示 x 到根的奇偶距離（mod 2）。合併邊 (u,v) 時：

• 若根不同，合併並設置 val[root_u] = val[u] ^ val[v] ^ 1（邊長為 1，奇偶翻轉）。
• 若根相同，檢查 val[u] ^ val[v] 是否為 1，否則發現奇環。

int find(int x) {
    if (fa[x] != x) {
        int p = fa[x];
        fa[x] = find(fa[x]);
        val[x] ^= val[p];
    }
    return fa[x];
}

void unite(int u, int v) {
    int fu = find(u), fv = find(v);
    if (fu != fv) {
        fa[fu] = fv;
        val[fu] = val[u] ^ val[v] ^ 1;
    } else if ((val[u] ^ val[v]) == 0) hasOddCycle = true;
}

完整判斷邏輯

// 讀入圖
// 初始化並查集 / color 數組
// 遍歷所有邊 unite / dfs
// 檢查連通性：所有點 find 根是否相同
// 輸出：hasOddCycle && connected ? "YES" : "NO"

複雜度

DFS/BFS O(n+m)；並查集 O((n+m) α(n))。三種方法均滿足 n,m ≤ 10⁵。