图论：二分图

二分图

简介

无向图中的顶点可以分为两个交集为空的集合X和Y，对于图中的每条边，其中一个端点在X中，另外一个端点在Y中，且X和Y内部的顶点之间没有边。

集合X和Y中每对顶点之间都有且仅有一条边的图称为完全二分图，可以记作$K_{n,m}$，n和m分别为X和Y集合中的顶点个数。

判定方法

染色法：

每次选择一个未被染色的顶点x，先将其染为黄色，接着从x除法做dfs遍历x所在的连通块。

在dfs的过程中，假如现在枚举到了边u→v，如果v还没有被染色，则把v染成和u不同的颜色，否则如果u和v颜色相同，则说明此图不是二分图。

如果能顺利遍历完图中所有的连通块，则此图为二分图。

vector<int> edge[N];
int n, m, c[N];
//染色
bool dfs(int x)
{
    for (auto y : edge[x])
        if (!c[y])
        {
            c[y] = 3 - c[x];
            if (!dfs(y))
                return false;
        }
        else if (c[x] == c[y])
            return false;
    return true;
}
bool check()
{
    memset(c, 0, sizeof c);
    for (int i = 1; i <= n; i++)
        if (!c[i])
        {
            c[i] = 1;
            if (!dfs(i))
                return false;
        }
    return true;
}

二分图最大匹配

简介

将二分图G=<V,E>的顶点集V拆分为$V_1$，$V_2$，$|V_1|\le |V_2|$，选取一些边E’⊆E；

如果E’中任意两条边都没有相同的顶点，则称E’为G的匹配；

G中边数最多的匹配称为G的最大匹配，其中包含的边数称为G的匹配数；

如果G的最大匹配包含的边数$=|V_1|$，则称此匹配为完备匹配。

一组最大匹配，也是完备匹配。

交错路径：如果P是G中的一条路径，并且对于P上每一对相邻的边（端点包含同一个顶点），都满足其中一条在匹配M中，而另一条不在。

增广路径：一条交错路径的路径的起点和终点都未被匹配的路径叫做增广路径。

如果我们能找到增广路径P，那么M⊕P（对于一条边，如果它在M中出现不在P中出现或是在P中出现不在M中出现）就是一组更优的匹配。

判定（匈牙利算法）

通过不断寻找新的增广路，来优化现有的匹配。

时间复杂度：$O(nm)$

vector<int> edge[N];
int n, m, n1, n2, v[N];
bool b[N];
bool find(int x)
{
    b[x] = true;
    for (auto y : edge[x])
    {
        if (!v[y] || (!b[v[y]] && find(v[y])))
        {
            v[y] = x;
            return true;
        }
    }
    return false;
}
int match()
{
    int ans = 0;
    memset(v, 0, sizeof v);
    for (int i = 1; i <= n1; i++)
    {
        memset(b, false, sizeof b);
        if (find(i))
            ++ans;
    }
    return ans;
}

最大独立集

在图中选出最多的点，满足他们两两之间没有边相连

$最大独立集=n-最大匹配数$

最小点覆盖

选出最少的点至少包含二分图的每条边的两个点中的一个。

$最小点覆盖=最大匹配数$

棋盘转二分图

vector<int> edge[N];
int n, m, n1, n2;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int a[N][N]; //棋盘中不能放置的点
int r[N][N]; //存储棋盘（二分图）中左右两边点的编号

scanf("%d%d", &n, &m); // n*n的棋盘，有m个不可放置的点
memset(a, 0, sizeof a);
n1 = n2 = 0;
for (int i = 1; i <= m; i++)
{
    int x, y;
    scanf("%d%d", &x, &y);
    a[x][y] = 1;
}
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        if (!a[i][j])
            if ((i + j) & 1)
                r[i][j] = ++n2;
            else
                r[i][j] = ++n1;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        if (!a[i][j] && !((i + j) & 1))
            for (int k = 0; k < 4; k++)
            {
                int x = i + dx[k], y = j + dy[k];
                if (x < 1 || x > n || y < 1 || y > n || a[x][y])
                    continue;
                edge[r[i][j]].push_back(r[x][y]);
            }

转换成二分图问题（拆点）

将一个点拆成一个进去的点和一个出去的点，观察是否可以装换成匹配问题。