HDOJ 3478 Catch - 染色法判斷二分圖在追捕問題中的應用

小偷在無向圖中移動，每時刻必須移動到相鄰節點（不可原地停留）。警察想知道：是否存在某個時刻，使得小偷可能出現在圖中任意節點？

問題建模：二分圖與奇偶性

小偷每步移動改變「層次」（距離起點的步數奇偶性）。若圖是二分圖，節點可分為黑白兩色，小偷每步必在兩色間跳轉。若在某時刻 t 能到達所有節點，則所有節點必須在同一時刻可達，這要求圖中不存在奇環（即必須是二分圖），且圖必須連通。

反之，若圖連通且為二分圖，從起點出發，經過足夠長時間（具體為圖的直徑或更大），小偷可以到達任意節點（因為二分圖中任意兩點間路徑長度奇偶性固定，通過繞環可調整步數）。

算法流程

1. 判斷圖是否連通（DFS/BFS 從 0 號節點遍歷，檢查訪問節點數是否為 N）。
2. 判斷圖是否為二分圖（染色法 DFS/BFS，檢查是否有相鄰同色節點）。
3. 若連通且為二分圖，輸出 YES，否則 NO。

代碼關鍵點

// 染色法判二分圖
bool dfs(int u, int c) {
    if (color[u] != 0) return color[u] == c;
    color[u] = c;
    for (int v : adj[u])
        if (!dfs(v, -c)) return false;
    return true;
}
// 主流程
if (connected && bipartite) puts("YES");
else puts("NO");

總結

這道題將「追捕問題」巧妙轉化為圖論中的「連通性」與「二分圖」判定。核心在於理解小偷移動的奇偶性約束與二分圖性質的等價性。染色法判二分圖是基礎圖算法必會技能。