二分图 染色法判定二分图 匈牙利算法

RainPPR

二分图

定义

当且仅当图中不含奇数环

可以将所有节点划分成两部分，使得每一部分内没有边。

构造

遍历每一个点
如果点没有被分组，放到１组
与这个点联通的所有点，放到２组

染色法判定二分图

用１和２区分不同颜色，用０表示未染色
遍历所有点，对未染色的点进行dfs，默认染成１
由于某个点染色成功不代表整个图就是二分图，因此只有某个点染色失败才能立刻exit
染色失败相当于存在相邻的２个点染了相同的颜色

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

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

bool dfs(int u, int c)
{
        color[u] = c;

        for (int i = h[u] ; i != -1 ; i = ne[i])
        {
                int j = e[i];
                if (!color[j])
                {
                        if (!dfs(j, 3 - c))
                                return false;
                }
                else if (color[j] == c)
                        return false;
        }

        return true;
}

int main()
{
        scanf("%d %d", &n, &m);

        memset(h, -1, sizeof h);

        while (m--)
        {
                int a, b;
                scanf("%d %d", &a, &b);
                add(a, b);
                add(b, a);
        }

        // 染色
        bool flag = true;
        for (int i = 1 ; i <= n ; ++i)
                if (!color[i])        // 未被染色
                        if (!dfs(i, 1))
                        {
                                flag = false;
                                break;
                        }

        if (flag)
                printf("Yes\n");
        else
                printf("No\n");

        return 0;
}

匈牙利算法

O(mn)，实际时间较小。

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 510, M = 100010;

int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];

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;
                        if ((match[j] == 0) || find(match[j]))
                        {
                                match[j] = x;
                                return true;
                        }
                }
        }
        return false;
}

int main()
{
        scanf("%d %d %d", &n1, &n2, &m);

        memset(h, -1, sizeof h);

        int a, b;
        while (m--)
        {
                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;
}

上次发的学习记录被人发现了（呵呵，不过也没什么），Y总讲课很有趣（现场debug，然后讲匈牙利算法用谈恋爱举例哈）。

myHeart98

膜拜大佬

gcode

感谢分享，分析很详细

czyr

c++看起来就头疼

lsy832

我还以为是打台球的二分法

yclm233

感谢大佬分享

alongzhenggang

lsy832 发表于 2023-1-7 19:01
我还以为是打台球的二分法

貌似也可以这样