二分图

如果一张无向图的顶点集可以分为两个不相交的非空子集 $A,B$，使得每条边的两个顶点分别属于这两个子集，那么称这张无向图为二分图。$A,B$ 分别称为二分图的左部和右部。

二分图判定

定理：一张无向图是二分图，当且仅当图中不含奇环（长度为奇数的环）。

染色法判定二分图：

1. 将图中的顶点染成两种颜色，相邻的顶点染成不同颜色。
2. 如果可以成功染色，则该图是二分图；否则，该图不是二分图。

伪码：

bool dfs(int x, int c) {
    col[x] = c;
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        if (!col[y]) {
            if (!dfs(y, 3 - c)) return false;
        } else if (col[y] == c) return false;
    }
    return true;
}

int main() {
    bool flag = true;
    for (int i = 1; i <= n; i++) {
        if (!col[i]) {
            if (!dfs(i, 1)) {
                flag = false;
                break;
            }
        }
    }
    if (flag) puts("YES");
    else puts("NO");
}

二分图的最大匹配

任意两条边都没有公共端点的边的集合被称为图的一组匹配。在二分图中，包含边数最多的一组匹配被称为二分图的最大匹配。

增广路：对于二分图的任意一组匹配 $S$，如果二分图中存在一条连接两个非匹配点的路径 $path$，使得非匹配边与匹配边在 $path$ 上交替出现，那么称 $path$ 是匹配 $S$ 的增广路，也称交错路。

增广路的性质：

1. 长度是 $n$ 奇数。
2. 路径上奇数边是非匹配边，偶数边是匹配边。

根据以上性质，我们知道非匹配边比匹配边多 $1$，如果把路径上所有边的状态取反，那么新得到的边集任然是一组匹配，并且匹配边数增加了 $1$。

进一步：二分图的一组匹配 $S$ 是最大匹配，当且仅当图中不存在 $S$ 的增广路。

匈牙利算法

1. 设 $S=\varnothing$，即所有边都是非匹配边。
2. 寻找增广路 $path$，把路径上所有边的状态取反，得到一个更大的匹配 $S^{\prime }$。
3. 重复步骤 $2$，直至图中不存在增广路。

如何寻找一条增广路？

从左部节点 $x$ 出发寻找一个匹配的右部节点 $y$。节点 $y$ 满足以下两个条件之一：

1. $y$ 本身是非匹配点。
2. $y$ 已经与左部节点 $x^{\prime }$ 匹配，但是从 $x^{\prime }$ 出发能够找到另一个右部节点 $y^{\prime }$ 与之匹配。

bool dfs(int x) {
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        if (!vis[y]) {
            vis[y] = 1;
            if (!match[y] || dfs(match[y])) {
                match[y] = x;
                return true;
            }
        }
    }
    return false;
}

int main() {
    for (int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof vis);
        if (dfs(i)) ans++;
    }
}