染色法
-
思路
$for(i = 1; i<= n; i++)$
$if(i未染色)$
$dfs(i,1)$
二分图:当且仅当图中不含奇数环,若存在奇数环,则不为二分图。
我们可以把图中所有点划分到两边,使得所有的边都是在集合之间,集合内部没有边。这里我们可以采用染色法来进行点的划分,若节点i的颜色为1,那么和他连接的节点就必须为颜色2。从二分图的定义我们可以得知只要图中不含有奇数环,那么染色过程中就一定没有矛盾。
我们对所有节点进行遍历,只要节点 $i$没有染颜色,我们就用深度优先遍历把 $i$所在的连通块整个染一遍,只要一个连通块中的某一个点记录了颜色,那么其余所有点的颜色就都全部确定了。
在深度优先遍历的过程中,只要 $dfs$ 返回的是 $false$,我们就认为有矛盾发生 ,即当前染色过程中出现了颜色冲突,说明该图存在奇数环,也就不是二分图。
color
数组表示当前节点的颜色, 所有的边用邻接表进行存储。
-
步骤
-
对所有节点和边进行初始化,使用邻接表存储。
- 对所有节点进行遍历,依次进行染色。
- 如果该节点没有染色,进入深度优先遍历进行染色,任意给定一个颜色值。
-
深度优先遍历该节点所有边的节点,只要没染色就继续深度优先遍历进行染色,若节点 $j$ 已经染色且与该节点的颜色相同,即为染色失败,说明该图存在奇数环,返回 $false$ 。否则,在所有节点遍历完之后返回 $true$。
-
例题
给定一个 $n$ 个点 $m$ 条边的无向图,图中可能存在重边和自环。
请你判断这个图是否是二分图。
-
输入格式
第一行包含两个整数 $n$ 和 $m$。
接下来 $m$ 行,每行包含两个整数 $u$ 和 $v$,表示点 $u$ 和点 $v$ 之间存在一条边。
-
输出格式
如果给定图是二分图,则输出 Yes
,否则输出 No
。
-
数据范围
$1≤n,m≤105$,
-
输入样例:
4 4
1 3
1 4
2 3
2 4
-
输出样例:
Yes
-
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5+10, M = 2e5+10;
int color[N], dist[N], n,m;
int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
e[idx]= b;
ne[idx] = h[a];
h[a] = idx++;
}
bool dfs(int ver, int c)
{
color[ver] = c;
for(int i = h[ver]; 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()
{
cin >> n >> m;
memset(h, -1, sizeof(h));
while(m--)
{
int a,b;
cin >> 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("No");
else puts("Yes");
return 0;
}