二分图

发表于 更新于 分类于 ，
本文字数： 1.7k
  • 染色法判定二分图
  • 匈牙利算法求二分图最大匹配

    二分图概念

可以将所有点分至两个集合，所有的边都存在于两个集合之间，集合内部不存在边（二分图中不含奇数环）

染色法（二染色）判定二分图

思路

通过DFS或BFS实现 依次判断每个点是否被染过色，如果没有染过色则将其染色，并将与其相连的所有点通过DFS或BFS的方式染色，在染色的过程中如果出现冲突则证明不是二分图

代码

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
// 染色过程
bool dfs(int x, int color)
{
    st[x] = color;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            if (!dfs(j, 3 - color))
                return false;
        }
        else if (st[j] == color)
            return false;
    }
    return true;
}

// 遍历所有点
bool flag = true;
for (int i = 1; i <= n; i++)
{
    if (!st[i])
        if (!dfs(i, 1))
        {
            flag = false;
            break;
        }
}

匈牙利算法

思路

给定一个二分图，求其最大匹配数（匹配成功为二分图中不存在两条边共用一个点，最大匹配数则是求满足上述条件最多有多少条边） 匈牙利算法具体思路为，选择一个集合，建立 match[N]（用于储存另一个集合匹配到所选集合中的哪一个点） 和 st[N] （用于标记第二个集合中的点在匹配过程中是否被遍历过） 遍历所选集合的所有点进行匹配操作，遍历过程中每次都要将 st 数组全部初始化为 false 匹配过程中要检查是否存在与其相连的另一个集合中的点可以匹配成功 检查过程大致为：如果一个点的 st 为 false，则标记为 true，并且检查其 match

  • 如果match为 0，则更新 match 为当前被选集合中的点，返回匹配成功
  • 如果match不为 0，则使用递归的方式检查 match 储存的点是否还有其他可选择的与其相连的另一个集合中的点，如果存在则更新 match数组，并返回匹配成功

如果检查所有的点都不满足匹配成功的条件则匹配失败

代码

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
#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 1e5 + 10;

int n1, n2, m;

int res;

int h[N], e[M], ne[M], idx;

int st[N], match[N];

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

bool hungary(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0  hungary(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d%d", &n1, &n2, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
    }
    for (int i = 1; i <= n1; i++)
    {
        memset(st, false, sizeof st);
        if (hungary(i))
            res++;
    }
    cout << res;
    return 0;
}