二分图的染色判定 - NOI提高级教程

📖 算法原理：二部图与奇环判定定理

二分图（Bipartite Graph）又称偶图。若能把无向图 $G = (V, E)$ 的顶点集 $V$ 划分为不相交的两个集合 $V_1$ 与 $V_2$，使得任意一条边的两个端点分别属于不同集合，则称该图为二分图。

📐 二分图核心判定定理

一个无向图是二分图的充分必要条件是：图中不含有奇数长度的环（简称奇环，Odd Cycles）。

染色法原理： - 任意选择一个未染色的节点开始进行深搜（DFS）或广搜（BFS）。 - 将当前节点染成颜色 1（红色），并将其所有相邻节点染成颜色 2（蓝色）。 - 递归将邻居的邻居染为相反颜色。 - 若在遍历中发现某条边连接了两个已经染成相同颜色的相邻节点，则说明存在奇环，判定为非二分图！

选择测试图：

演示速度：

选择测试图并点击"开始染色判定"观察无向图交叉染色全过程。

🕸️ 二阶交叉染色 DFS 递归状态机 (Coloring State Machine)

int color[MAXN]; // 记录节点颜色：0未染，1红，2蓝

bool dfs(int u, int c) {
    color[u] = c; // 将当前节点 u 染为颜色 c
    for (int v : g[u]) {
        // 相邻节点 v 已经染过色，且颜色与 u 相同
        if (color[v] == c) {
            return false; // 发现同色相邻，说明存在奇环，非二分图！
        }
        // 若 v 未染色，则递归将其染成相反颜色 3 - c
        if (color[v] == 0) {
            if (!dfs(v, 3 - c)) return false;
        }
    }
    return true;
}

bool checkBipartite() {
    memset(color, 0, sizeof(color));
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) {
            if (!dfs(i, 1)) return false;
        }
    }
    return true;
}

📋 递归染色步骤历史