UVALive 3523 Knights of the Round Table：雙連通分量 + 二分圖判定

題目大意

n (≤1000) 位騎士，m (≤10⁶) 對互相仇恨關係。圓桌會議規則：

1. 相鄰騎士不能互相仇恨
2. 參會騎士數必須為奇數（≥3）

無法參加任何合法會議的騎士須被開除。求開除人數。

圖論建模

• 建立**補圖**：原圖中無邊（不仇恨）的騎士對在補圖中連邊
• 合法會議 ⇔ 補圖中的**奇環**
• 騎士能參會 ⇔ 所在補圖連通塊的**雙連通分量**中存在奇環

核心定理

一個無向圖中，點 u 能參與某個奇環 ⇔ u 所在的**雙連通分量**是**非二分圖**（即包含奇環）。

算法流程

1. 構建補圖（邊數 = n(n-1)/2 - m，稠密圖用鄰接矩陣或 bitset）
2. Tarjan 算法求雙連通分量（邊雙連通/點雙連通均可，此處用點雙連通）
3. 對每個雙連通分量，判斷是否為二分圖（BFS/DFS 染色）
4. 若某分量非二分圖，標記其中所有點為「可參會」
5. 答案 = n - 可參會騎士數

關鍵代碼框架

const int MAXN = 1005;
vector G[MAXN], bcc[MAXN];
stack> S;
int dfn[MAXN], low[MAXN], bccno[MAXN], dfs_clock, bcc_cnt;
bool iscut[MAXN];

void dfs(int u, int fa) {
    dfn[u] = low[u] = ++dfs_clock;
    int child = 0;
    for (int v : G[u]) {
        if (!dfn[v]) {
            S.push({u,v});
            child++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                iscut[u] = true;
                bcc_cnt++;
                while (true) {
                    auto e = S.top(); S.pop();
                    if (bccno[e.first] != bcc_cnt) { bcc[bcc_cnt].push_back(e.first); bccno[e.first]=bcc_cnt; }
                    if (bccno[e.second] != bcc_cnt) { bcc[bcc_cnt].push_back(e.second); bccno[e.second]=bcc_cnt; }
                    if (e.first==u && e.second==v) break;
                }
            }
        } else if (dfn[v] < dfn[u] && v != fa) {
            low[u] = min(low[u], dfn[v]);
            S.push({u,v});
        }
    }
    if (fa == -1 && child == 1) iscut[u] = false;
}

bool is_bipartite(const vector& comp) {
    unordered_map color;
    queue q;
    for (int u : comp) if (!color.count(u)) {
        color[u] = 0; q.push(u);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : G[u]) {
                if (bccno[v] != bccno[u]) continue; // 只看分量內部邊
                if (!color.count(v)) { color[v] = color[u]^1; q.push(v); }
                else if (color[v] == color[u]) return false;
            }
        }
    }
    return true;
}

複雜度分析

• 補圖構建：O(n²) 邊，n=1000 時 5×10⁵ 邊可接受
• Tarjan：O(V+E)
• 二分圖判定：O(V+E)
• 總體：O(n²)，符合限制

關鍵優化

• 用 `bitset<1000>` 存儲鄰接矩陣，補圖遍歷極快
• 雙連通分量內部判斷二分圖時，只遍歷分量內的邊
• 孤立點（補圖度為 0）直接標記為不可參會