二分图

Created2021-03-09Updated2021-03-09

二分图

二分图

定义

设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

判断条件：当且仅当图中不含奇数环（充要条件）

染色法判断二分图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100010;
struct node
{
    int next,to;
}e[N*2];
int head[N],color[N];
int cnt=0,flag=1;
int n,m;
void add(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
int dfs(int u,int c)
{
    color[u]=c;
    for(int i=head[u];i;i=e[i].next)
    {
        int to=e[i].to;
        if(!color[to])
        {
            if(!dfs(to,3-c))return 0;//出现矛盾
        }//3-c可以实现如果颜色是1就染2，如果是2就染1（0表示没染色）
        else if(color[to]==c)return 0;//出现矛盾的情况  
    }
    return 1;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        if(!color[i])//如果一个点没染过色，就染成1
        {
            if(!dfs(i,1))//出现矛盾
            {
                flag=0;
                break;
            }
        }
    }
    if(flag)cout<<"Yes";
    else cout<<"No";
    return 0;
}

匈牙利算法

二分图最大匹配

图的匹配

对于一张无向图 (V,E)，若存在一个边集 E′，满足 E′⊆E，且对于任意 p,q∈E′，p,q 没有公共端点，则称 E′ 为这张无向图的一组匹配。

二分图最大匹配

在二分图中，包含边数最多的一组匹配被称为二分图的最大匹配。

其他相关定义

对于任意一组匹配 S，属于 S 的边被称为匹配边，不属于 S 的边被称为非匹配边。

匹配边的端点被称为匹配点，其他点被称为非匹配点。

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

增广路的性质

  1. 长度为奇数。
  2. 奇数边是非匹配边，偶数边是匹配边。
  3. 如果把路径上所有边的状态（是否为匹配边）取反，那么得到的新的边集 S′ 仍然是一组匹配，并且匹配的边数增加了 1。

结论

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

匈牙利算法

时间复杂度

O(nm)，实际运行速度较快

主要过程

  1. 初始时设 S 为空集，即所有边都是非匹配边。
  2. 寻找增广路 path，把 path 上所有边的匹配状态取反，得到一个更大的匹配 S′。
  3. 重复第 2 步，直到图中不存在增广路。

寻找增广路

依次尝试给每一个左部点 x 寻找一个匹配的右部点 y。

y 与 x 匹配需满足下面两个条件之一：

  1. y 是非匹配点。
  2. y 已与 x′ 匹配，但从 x′ 出发能找到另一个 y′ 与之匹配。

例题模板

洛谷P3386 【模板】二分图最大匹配

题目描述

给定一个二分图，其左部点的个数为 n，右部点的个数为 m，边数为 e，求其最大匹配的边数。

左部点从 1 至 n 编号，右部点从 1至 m 编号。

输入格式

输入的第一行是三个整数，分别代表 n，m 和 e。

接下来 e 行，每行两个整数 u, v，表示存在一条连接左部点 u 和右部点 v 的边。

输出格式

输出一行一个整数，代表二分图最大匹配的边数。

输入输出样例

输入 #1

1
2
1 1 1
1 1

输出 #1

1
1

输入 #2

1
2
3
4
5
6
7
8
4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1

输出 #2

1
2

数据规模与约定

对于全部的测试点，保证：

  • 1≤n,m≤500。
  • 1≤e≤5×10^4。
  • 1≤u≤n，1≤v≤m。

不保证给出的图没有重边。

代码模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100010;
struct node
{
    int next,to;
}e[N*5];
int head[N],match[N];//match[x]存储的是右边的点对应的左边的匹配点
int vis[N];
int cnt=0;
int n1,n2,m;
int res=0;
void add(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
int find(int x)
{
    for(int i=head[x];i;i=e[i].next)
    {
        int to=e[i].to;
        if(!vis[to])
        {
            vis[to]=1;//防止这个右边的点在递归时被再次搜到，即每个右边的点只考虑一次
            if(match[to]==0 or find(match[to]))
            {
                match[to]=x;
                return 1;
            }//如果它连到的右边的点还没有匹配，或者我们能为它右边点曾经匹配的左边找到新的匹配，那么就可以让它匹配当前的左边
        }
    }
    return 0; //配对失败
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n1>>n2>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);//虽然是无向边，但是匹配的过程中更换边这样的操作是单向进行的，因此存一条即可
    }
    
    for(int i=1;i<=n1;i++)
    {
        memset(vis,0,sizeof(vis));
        if(find(i))res++;
    }
    cout<<res;
    return 0; 
}