染色法判定二分图−三种语言实现全解析
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
思路
染色法判定二分图
1.算法原理
染色法使用dfs思想,每次染色对下一个子节点染色为父节点异色节点,若染色过程中,出现要染色
点与父节点相同,则不为二分图
2.算法细节
1.染色过程:只会对无色的点进行染色,有色点出现冲突才返回假
bool dfs(int x, int y){
color[x] = y;
for(int i=h[x]; i!=-1; i=ne[i]){
int u = e[i];
if (color[u] == y) return false;//若邻点已经和自己颜色相同,说明不为二分图
//一旦染色过程中出现冲突返回false
if(!color[u]){
if(!dfs(u, 3 - y)) return false;//3-y:1邻点染2, 2邻点染1
}
}
//染色无误,为二分图
return true;
}
2.二分图不一定是树,未必是联通的!因此每次都从1开始染色的话
势必不会产生冲突,每个二分图一部分都可以完美染色
bool flag = true;
for(int i=1; i<=n; i++)
if(!color[i]){
//优先染1,一旦染色出现冲突,证明图不为二分图
if(!dfs(i, 1)) {
flag = false;
break;
}
}
二刷感悟:
图方便直接让dfs中,如果子节点没有颜色,return dfs(son, 3 - y)
,这里不能想当然的直接return,如果return相当于只在dfs递归到没有子节点的叶节点就返回为真了,而我们真正想要的是遍历完整个父节点的所有子树,而直接return
是返回dfs递归的一条路径。
1. java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
static int N = (int) 2e5 + 10, n, m, idx;
static int[] e = new int[N];
static int[] ne = new int[N];
static int[] h = new int[N / 2];
static int[] color = new int[N / 2];
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
static boolean dfs(int x, int y) {
color[x] = y;
for (int i = h[x]; i != -1; i=ne[i]) {
int j = e[i];
if(color[j] == y) return false;
if (color[j] == 0){
if(!dfs(j, 3 - y))
return false;
}
}
return true;
}
public static void main(String[] args) throws IOException {
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
Arrays.fill(h, -1);
for (int i = 0; i < m; i++) {
String[] s2 = br.readLine().split(" ");
int a = Integer.parseInt(s2[0]);
int b = Integer.parseInt(s2[1]);
add(a, b);
add(b, a);
}
boolean flag = true;
for (int i = 1; i <= n; i++) {
if (color[i] == 0) {
if (!dfs(i, 1)) {
flag = false;
break;
}
}
}
if (flag) System.out.println("Yes");
else System.out.println("No");
}
}
2. python3代码(bfs, python的dfs因为树的深度问题会爆栈,dfs参考C++代码)
N = int(1e5+10)
M = 2 * N
h = [-1] * N
e = [0] * M
ne = [0] * M
idx = 0
color = [0] * N
def add(a, b):
global idx
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx += 1
def bfs(u):
q = []
hh, tt = 0, -1
#默认染色1,邻点染色2
q.append([u, 1])
tt += 1
while hh <= tt:
x, y = q[hh]
hh += 1
color[x] = y
i = h[x]
while i != -1:
j = e[i]
if not color[j]:
#无色则染异色入队
q.append([j, 3 - y])
tt += 1
elif color[j] == y:
return False
#这里为什么同色没有处理是因为根据bfs
#一旦一个点已经染色,势必它的邻点直到末尾都已染色
i = ne[i]
return True
if __name__ == '__main__':
n, m = map(int, input().split())
for i in range(m):
a, b = map(int, input().split())
add(a, b)
add(b, a)
flag = True
for i in range(1, n):
#无色即bfs,这里是因为二分图未必是整体联通的
if not color[i]:
if not bfs(i):
flag = False
break
if flag: print('Yes')
else: print('No')
3. C++ 代码 (DFS)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx;
int n, m;
int color[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool dfs(int x, int y)
{
color[x] = y;
for(int i=h[x]; i!=-1; i=ne[i])
{
int u = e[i];
//若邻点已经和自己颜色相同,说明不为二分图
if (color[u] == y) return false;
//3-y:1邻点染2, 2邻点染1
//一旦染色过程中出现冲突返回false
if(!color[u])
{
if(!dfs(u, 3 - y)) 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])
{
//优先染1,深度遍历染色整个图
//一旦染色出现冲突,证明图不为二分图
if(!dfs(i, 1)) {
flag = false;
break;
}
}
if(flag) puts("Yes");
else puts("No");
return 0;
}