染色法判定二分图
二分图
1. 二分图存在性,染色法($O(n + m)$)
2. 二分图的匹配,匈牙利算法(最坏$O(m,n)$,实际速度远快于此)
染色法判断二分图是否存在
二分图存在当且仅当不存在奇数环,换句话就是染色没有冲突就说明存在二分图
充分性证明
如果一个图是二分图,那么它一定不存在奇数环
假设图存在奇数环,并且它是二分图。易得,该假设不成立,所以二分图不存在奇数环
必要性证明
如果不存在奇数环,那么它一定是二分图
首先,无环图一定可以被二分,其次偶数环可以被均分。所以该假设成立
算法流程
我们用$color$[ ]数组记录每一个点它染得颜色,对于任意一个连通块来说,只要其中一个点的颜色确认了,那么其他点的颜色都可以确认。
我们染色时(遍历),如果该点没被染色,那我们就去染色。如果染色了,就看是不是存在冲突,如果冲突了,染色失败,不存在二分图,反之存在二分图。
因为给的图不一定是一个连通块,所以我们要对每个点都要遍历一遍(遍历过的进行标记,防止二次遍历)
图的存储与遍历
由于需要遍历临边并且是稀疏图,所以这里使用邻接表存储图
遍历可以采用深度优先遍历或者宽度优先遍历,这里因为$dfs$写的短,我们按$dfs$写
染色
$1$和$2$,表示两种颜色,状态转移时候,相邻点的颜色就是$3$减去当前点的颜色
代码
#include <cstring>
#include <iostream>
#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) puts("Yes");
else puts("No");
return 0;
}