二分圖

簡介

二分圖 (Bipartite Graph) 的概念就是一張存在兩個點集合組成的圖，且兩個點集內部沒有邊。

簡單來說就是，如果把每個節點都染成黑或白兩色，那每個黑節點的相鄰節點一定都是白的，白節點的相鄰節點一定都是黑的，如果沒辦法滿足這個條件就是不合法。

這個概念就是 DFS 的應用之一！

實作方式

這邊我們要開一個 c[] 陣列用來記錄顏色，1 代表白色 2 代表黑色，然後一邊把每個節點染色一邊走訪整張圖：

bool valid = true;

void dfs(int v) {
    for (auto u : g[v]) {
        // 如果這個節點已經被拜訪過
        if (c[u]) {
            // 不合法的情況
            if (c[u] != 3 - c[v]) {
                valid = false;
            }
            continue;
        }
        // 根據節點 v 的顏色分配新顏色給節點 u
        c[u] = 3 - c[v];
        dfs(u);
    }
}

c[1] = 1;
dfs(1);

這邊用到一了個小技巧：因為我們是透過 1 跟 2 來當兩個顏色，所以其實只要用 3 去減就可以得到另外一個顏色了。