二分图

lrx___ · 2024-12-16 19:29:51 · 算法·理论

二分图

1 定义

二分图是指一类图，可以将图中的点分为两组，满足所有的边都连接不同组的点。举个例子：

可以分为 (1,2) 与 (3,4) 两组，满足以上条件。

2 判定

先来简单地判定一下。

首先，没有环的图一定是二分图。因为没有环的图可以看做多棵树构成的森林，每棵树之间互不影响，所以只需考虑单棵树。

我们把深度为奇数的结点放在一组，为偶数的结点放在另一组。可以发现，一条边一定是连接两个深度相差为 1 的点，换句话说就是它们的奇偶性不同，因此所有边都连接不同组的结点，满足二分图的定义。

那么有环的图呢？

这样环上的点需要交替染色。我们指定一个点为第一组，则交替过去以后，如果环的长度为偶数，则最后一个点在第二组，满足二分图的定义。如果长度为奇数，则最后一个点也在第一组，就不满足二分图的定义了。

因此一个图是二分图，必定满足没有奇环。反过来讲，如果一个图没有奇环，则这个图是二分图。

那么如何实现呢？

通常有两种方式：染色法和扩展域并查集。

染色法的思想是：对于每个连通块，先指定一个点的组，然后就可以计算出其他所有点的组。如果互相矛盾了，则不是二分图。

可以用 DFS 实现。下面是代码：

bool vs[N],color[N],ans=true;
// vs[u] 表示 u 是否访问过，color[u] 表示 u 属于第几组
void dfs(int u,int father){
    vs[u]=true;
    // 遍历临边 v
    for(int& v:g[u]){
        if(v==father) continue;
        if(!vs[v]){
            // 如果没有访问过就染色并 DFS
            color[v]=color[u]^1;
            dfs(v,u);
        }else{
            // 否则判断是否矛盾
            if(color[u]==color[v]){
                ans=false;
                return;
            }
        }
    }
}

// 主函数中
for(i=1;i<=n;++i)
    if(!vs[i])
        dfs(i,0);

扩展域并查集的思想是：将每个点拆成两个点，分别表示这个点在那个组的情况。

遍历每条边，将同组的点合并。最后如果两点在同一组，则表示根据这个点的组，可以推出另一个点的组。

如果第一组的 i 和第二组的 i 相连，则不是二分图。

我们分别举个例子。设 i 的第一个点为 i，第二个点为 i+n。

对于上面那个图，我们有 8 个点。

对于边 (1,3)，我们合并 1 与 7,3 与 5。

对于边 (1,4)，我们合并 1 与 8,4 与 5。

对于边 (2,3)，我们合并 2 与 7,3 与 6。

此时 1,2,7,8 在同一组中，3,4,5,6 在同一组中。不存在 i 与 i+4 在同一组，所以该图为二分图。

对于这个图：

我们会合并 (1,6),(2,5),(1,7),(3,5),(2,7),(3,6),(1,8),(4,5)，最后的结果是 1~8 都合并到了一个组，显然存在 i 和 i+4 在同一组，因此该图不是二分图。

3 最大匹配

匹配的定义：

选出一些边，使得每个点最多连接 1 条边。

还是上面那张图，我们可以选 (1,4) 和 (2,3)，但不能选 (1,3) 和 (1,4)，因为 1 连接了两条边。

最大匹配是指选出边数最多的匹配。

我们考虑这样一个问题：

有 N 个人和 M 个房间。第 i 个人愿意住在 c_i 个房间，分别为 a_{i,1},a_{i,2},\dots,a_{i,c_i}。每个人只选一个房间，每个房间只能住一个人，问最多能让多少人住？

把人看成左侧的点，房间看成右侧的点，如果 i 愿意住在 j，则连边 i \to j。此时答案就是最大匹配。

求最大匹配通常由两种方法：匈牙利算法和最大流。这里讲一下匈牙利算法。

3.1 匈牙利算法

思想：枚举每个左侧点。如果该点能成功匹配，要么找一个还没匹配的右侧点，要么找一个匹配了的右侧点，让它所匹配的左侧点再换一个匹配。

bool visited[M];
int match[M];
// match[i]: 右侧点 i 所匹配的左侧点
bool dfs(int u){
    // 为左侧点 u 找一个匹配
    for(int& v:g[u]){
        // 枚举可以匹配的点
        if(!match[v]||dfs(match[v])){
            // 如果 v 还没匹配或者可以给 match[v] 换一个匹配
            match[v]=u;
            return true;
        }
    }
    // 无法匹配
    return false;
}

实际上每个右侧点只需访问一次。因为如果它还没匹配或者可以换，则直接匹配并结束；如果它既匹配了也不能换，那么后面再访问它就是无用功，因此便可以用 visited 数组标记：

bool visited[M];
int match[M];
// match[i]: 右侧点 i 所匹配的左侧点
bool dfs(int u){
    // 为左侧点 u 找一个匹配
    for(int& v:g[u]){
        // 枚举可以匹配的点
        if(!visited[v]){
            // 只访问有可能匹配的点
            visited[v]=true;
            if(!match[v]||dfs(match[v])){
                // 如果 v 还没匹配或者可以给 match[v] 换一个匹配
                match[v]=u;
                return true;
            }
        }
    }
    // 无法匹配
    return false;
}

// 主函数中
ans=0;
for(i=1;i<=n;++i){
    memset(visited+1,0,m);
    // 清空visited[1]~visited[m]
    ans+=dfs(i);
    //如果 i 能匹配
}

共有 N 次匹配，每次匹配会遍历所有点和边，所以时间复杂度为 \mathcal{O}(VE)。

(写一下代码)

<!-->

3.2 最大流

建立源点 S 和汇点 T，S 向每个左侧点连容量为 1 的边，每个右侧点向 T 连容量为 1 的边。如果左侧点 i 可以匹配右侧点 j，则 i 向 j 连容量为 1 的边。此时最大流就是最大匹配数。

这里给出最大流比较容易理解的定义：

每次找一条从 S 到 T 的路径，然后从 S 走到 T。边的容量就是这条边最多走的次数。此时最大流即为能找到的最多的路径数。

在这里，S 向每个左侧点、每个右侧点向 T 连容量为 1 的边代表每个点只能匹配一次，中间的边容量为 1 代表每个边只能选一次。

还是以那张图为例。我们可以选出两条路径：(S \to 1 \to 4 \to T),(S \to 2 \to 3 \to T)。因此最大流为 2。

求最大流的时间复杂度上界为 \mathcal{O}(V^2E)，但实际上很难达到上界。在最大匹配的模板题中，最大流的时间显著优于匈牙利。但最大流写起来比匈牙利算法麻烦的多，遇到二分图最大匹配的题目时，应首选匈牙利算法。

<-->

3.3 例题

例题 洛谷-P2756

将英国飞行员看做左侧点，外籍飞行员看做右侧点，即为二分图最大匹配。

例题 洛谷-P2765

这是一个比较有思维难度的题。

对于可以匹配的一对点，我们从小的数连向大的数。这是一个有向无环图。对于图上的一条路径，我们可以把路径上的点依次放到柱子上。这样问题就转化成了：在图中选一些路径，使得这些路径覆盖了所有点且没有交。

只要选出的路径数 <=n，则这个方案就是合法的。于是我们可以二分点的数量，然后计算匹配这些点至少需要的路径数。

那么应该如何计算呢？

这个问题有一个关键点。我们单独看这些路径，不考虑没选入路径的边，就会发现路径数 = 点数 - 路径中的边数。点数是固定的，因此要让路径数更少，我们需要让路径中的边数更多。

也就是说，对于每个点，我们需要选择一个出点（可以匹配的点），然后连一条边。最后要让匹配到出点的点数最多。

这就是一个二分图最大匹配问题。

我们整理一下步骤：

1. 二分放多少个球。

2. 需要求出放这些球需要的最小柱子数，即路径数。

3. 建图：对于每个点 i，如果 j>i 并且 i+j 是完全平方数，则 i 向 j 连边。

4. 求出二分图最大匹配，并与 n 比较。

实际上不需要二分。我们可以直接枚举答案，枚举时把新增的点和边加上，然后在原来图的基础上对新增的点匹配一遍，就能直接得到新的答案了。

（写一下代码）

4 其他题目

洛谷-5787

这道题由于边是动态的，用染色法比较难实现，因此使用扩展域并查集判断二分图。

如果我们按时间正着做，则需要实现以下操作：

1. 合并

2. 取消合并（保证之前合并过）

3. 判断是否有 i 和 i+n 已合并

如果保证每次取消合并时上一次没取消的合并和这次对应，则可以用可撤销并查集维护。但并不满足这个条件。

我们考虑将它放到线段树上。以时间为轴建立线段树。如果一条边在一段时间内连接了，则在线段树中对应的区间存储操作。

我们从上至下遍历整棵线段树：

1. 首先将该结点存储的操作执行

2. 分别遍历左右子区间

3. 将该结点的操作取消

这样到达每个叶子结点时，图的状态就和实际状态相同，并且满足了上面的条件，可以用可撤销并查集维护。