POJ 2942 Knights of the Round Table：點雙連通分量 + 奇環檢測

題目大意

N 個騎士，M 對互相憎恨關係。圓桌會議要求：(1) 憎恨者不相鄰 (2) 參會人數為奇數。無法參加任何合法會議的騎士將被開除。求開除人數。

核心轉化

• 構建補圖：原圖憎恨邊 ⇒ 補圖可相鄰邊
• 問題轉化：在補圖中找奇環（奇數長度環）
• 點雙連通分量性質：若一個塊含奇環，則該塊所有點都在某個奇環上

算法流程

1. 構建補圖邊
2. Tarjan 算法求點雙連通分量（用棧存邊）
3. 對每個分量，交叉染色法檢測奇環
4. 含奇環的分量中所有點標記為「可參會」
5. 答案 = N - 可參會騎士數

關鍵代碼片段

// Tarjan 求點雙連通分量
void dfs(int u, int fa) {
    low[u] = dfn[u] = ++tot;
    for (int v = 1; v <= n; v++) if (edge[u][v] && u != v) {
        if (!vis[v]) {
            vis[v] = 1;
            sta[++cnt] = {u, v};
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (dfn[u] <= low[v]) {
                // 彈出棧中邊形成一個分量
                sum++;
                do {
                    cur = sta[cnt--];
                    bcc[sum][cur.u] = bcc[sum][cur.v] = 1;
                } while (!(cur.u==u && cur.v==v));
                bcc[sum][u] = bcc[sum][v] = 1;
            }
        } else if (v != fa) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

// 交叉染色檢測奇環
void color(int u, int c, int bcc_id) {
    if (flag) return;
    for (int v = 1; v <= n; v++) if (edge[u][v] && in_bcc[bcc_id][v]) {
        if (vis[v] != -1) {
            if (vis[v] == c) flag = 1;
        } else {
            vis[v] = c ^ 1;
            color(v, c ^ 1, bcc_id);
        }
    }
}

關鍵結論

點雙連通分量中，若存在一個奇環，則該分量內所有頂點都位於某個奇環上。因此只需對每個分量整體判斷是否含奇環，無需逐點檢查。

複雜度

• 補圖構建：O(N²)，N ≤ 1000 可接受
• Tarjan：O(N + M')
• 奇環檢測：O(分量數 × 分量大小)
• 總計：~1 秒內