二分图

1. 染色法：时间复杂度 \(O(n+m)\)
2. 匈牙利算法：时间复杂度最坏 \(O(mn)\)，但实际运行时间一般远小于 \(O(mn)\)

染色法

二分图的定义：有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中，每个顶点集中没有边直接相连接的图(图中点通过移动能分成左右两部分，左侧的点只和右侧的点相连，右侧的点只和左侧的点相连)

染色法可以用来判断一个图是不是二分图。

定理：一个图是二分图当且仅当图中不含奇数环(边数为奇数的环)。

• 开始对任意一未染色的顶点染色。
• 判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色。
• 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。
• 通过DFS或BFS进行搜索。

例题：染色法判定二分图

代码模板：

/*
1. color数组初始化为0，被访问的点的颜色为1或2
2. 进入u，对u点染色
3. 枚举u的邻点v
（1）若v未访问，走进去，若返回有奇环，则一路返回有奇环
（2）若v已访问且v的颜色与u的颜色相同，则返回有奇环
4. 枚举完u的邻点，没有发现有奇环，则返回没有奇环
*/

int n; //n为点数
int h[N], e[M], ne[M], idx;  //邻接表存储图
int color[N];  //表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色

// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c) {
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (color[j] == -1) {
            if (!dfs(j, !c)) return false;
        } else if (color[j] == c) return false;
    }
    return true;
}

bool check() {
    memset(color, -1, sizeof color);
    bool flag = true;

    for (int i = 1; i <= n; i++) {
        if (color[i] == -1) {
            if (!dfs(i, 0)) {
                flag = false;
                break;
            }
        }
    }
    return flag;
}

匈牙利算法

例题：二分图的最大匹配