基础算法——二分图 -- 染色法判别二分图、最大匹配数（匈牙利算法）

二分图概念

二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。简单来说，二分图里面的所有边的两个顶点都不在一个集合中；
如图：

染色法判别二分图

染色法思路：开始对任意一未染色的顶点染色 -> 判断其相邻的顶点，若未染色则将其染上和相邻顶点不同的颜色，若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。bfs和dfs可以搞定！

例题：

#include 
#include 
#include 

using namespace std;

const int N = 200010;//无向边，所以每两个点都需要连两条边

int n, m;//n个点，m条边
int h[N], e[N], ne[N], idx;//邻接表存储图
int color[N];//表示各个点被染成了啥颜色，0表示未染色，1表示染成红色，2表示染成黑色

void add(int a, int b)//邻接表插入一条a->b的边
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool dfs(int u, int c)
{
    color[u] = c;//把该点染成c色
    
    //遍历所有u的邻边
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!color[j])//如果相邻的点没有被染色，则递归处理这个相邻的点
        {
            if(!dfs(j, 3 - c)) return false;
            //3 - 1 = 2; 3 - 2 = 1,
        }
        else if(color[j] == c) return false;//相邻的颜色一样，矛盾
    }
    
    return true;
}

int main()
{
    cin >> n >> m;//读入点和边
    memset(h, -1, sizeof h);//初始化邻接表
    
    while(m--)//处理边
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);//无向图
    }
    
    for(int i = 1; i <= n; i++)//遍历所有顶点
    {
        if(!color[i])//如果没有被染色
        {
            if(!dfs(i, 1))//染色该点，并递归处理它相邻的点
            {
                puts("No");//出现矛盾
                return 0;
            }
        }
    }
    puts("Yes");//全部染色成功
    
    return 0;
}
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
57
58
59
60
61
62
63
64
65

二分图的最大匹配数—匈牙利算法

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。1955年，库恩(W.W.Kuhn)利用匈牙利数学家康尼格(D.Kőnig)的一个定理构造了这个解法，故称为匈牙利法。
如图：首先x1会与y1相匹配；然后x2会与y2相匹配；x3发现y1已经被匹配了，而y2也被匹配完了，所以x3会让x1能不能换个匹配对象，结果x1就找到了y2，但是y2已经被x2给占了，就让x2能不能换个，x2就找到了y3，这时候x1匹配y2，x2匹配y3，x3从而就成功匹配了y1，最后x4匹配了y4，因此图中最大匹配数就是4（图中的图连线包括虚线和实线）

例题：

#include 
#include 
#include 

using namespace std;

const int N = 510, M = 100010;

int n1, n2, m;
int h[N], e[N], ne[N], idx;//邻接表，我们都是从左边来找右边的，所以两顶点之间不需要存储两条边
int match[N];//match[i] = j -> 表示i现在匹配的对象时j
bool st[N];//预定数组， st[i] = j -> 表示i现在被j给预定了，但不是最终结果 

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool find(int x)
{
    //遍历所有可以匹配的对象
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j])//如果在这一轮模拟匹配中,当前点没有被匹配
        {
            st[j] = true;//就匹配
            //如果j没有被匹配，或者原来的匹配对象能够预定其它的；则配对成功,更新match
            if(match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    cin >> n1 >> n2 >> m;
    memset(h, -1, sizeof h);//初始化邻接表
    
    while(m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    
    int res = 0;//最终结果，表示最大匹配数
    for(int i = 1; i <= n1; i++)//遍历左边所有顶点
    {
        memset(st, false, sizeof st);//因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
        if(find(i)) res++;
    }
    printf("%d\n", res);
    
    return 0;
}
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
57
58
59
60
61
62