2X岁，是学生です

0%

二分图

发表于 分类于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

二分图

本文时间复杂度中: $n$ 为节点数， $m$ 为边数。

二分图

点集 $V$ 可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。

当且仅当图中不含奇数环（环当中边的数量为奇数）时，才有可能是二分图。

染色法 $O(n + 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
57
58
59
60
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;
int h[N], e[M], ne[M], idx = 1;
int n, m;
int colors[N];

void myadd(int u, int v)
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

bool dfs(int u, int c)
{
    colors[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if (!colors[v])//先判断是否上过色，没上过色先用dfs上色
        {
            if (!dfs(v, 3 - c))//“3进制”
                return false;
        }
        else if (colors[u] == colors[v])//已上过色，直接比较颜色，这里还能处理掉自环
            return false;
    }
    return true;
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    while (m--)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        myadd(u, v), myadd(v, u);
    }
    memset(colors, 0, sizeof(colors));
    bool flag = true;
    for (int i = 1; i <= n; ++i)//遍历，防止有不连通的点染不上色
    {
        if (!colors[i])
        {
            if (!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }
    }
    if (flag)
        puts("Yes");
    else
        puts("No");
    return 0;
}

匈牙利算法 最坏 $O(m \times n)$，一般远小于 $O(m \times n)$

用于计算二分图的最大匹配。

二分图的匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称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 <cstdio>
#include <cstring>
using namespace std;

const int N = 510, M = 1e5 + 10;
int h[N], e[M], ne[M], idx = 1;
bool st[N];//为什么每次都要先置为flase呢？
//因为后来的点如果可以，就一定要抢走先匹配上的点的匹配，先匹配上的点就要重新找匹配，
//但是原来的匹配点已经被后来的占用了，为了防止这两个点互相抢当前匹配，就需要记录该状态
int mymatch[N];//记录右边与左边哪个点对应

void myadd(int u, int v)
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

bool myfind(int u)//判断当前左边集合中的点能否找到一个右边集合中还可用的配对
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int v = e[i];
        if (!st[v])//本轮中v点还未被匹配
        {
            st[v] = true;
            //要么这个匹配点没被用过；或者被用过，但是当前点抢占后，原来的点能找到新匹配
            if (!mymatch[v] || myfind(mymatch[v]))
            {
                mymatch[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int n1, n2, m;
    scanf("%d%d%d", &n1, &n2, &m);
    memset(h, -1, sizeof(h));
    while (m--)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        myadd(u, v);
    }
    int res = 0;
    memset(mymatch, 0, sizeof(mymatch));
    for (int i = 1; i <= n1; ++i)
    {
        memset(st, false, sizeof(st));//用于左边点集中一个点所有出边只被访问一次
        if (myfind(i)) ++res;
    }
    printf("%d", res);
    return 0;
}