搜索与图论 ---- 染色法判定二分图

染色法判定二分图

二分图的定义

二分图就是图中的集合（u，v）中都只包含点，而不包含边。

性质：二分图中不包含奇数环

何为奇数环：
奇数环就是环中边的数量是奇数

同样的，如果一个图是二分图，那么该图中就一定不会包含奇数环。
同样的，如果一个图中含有奇数环，那么该图就一定不会是二分图。

如何判断是否是二分图

想要判断是否是二分图，就要从二分图的性质出发，二分图中不包含奇数环，也就是说，如果我们遍历一张图，如果图中出现了奇数环，那么就说明改图不是二分图，反之则说明该图是二分图。

那么如何判断图中是否有奇数环呢？
我们采用染色法！！！

所谓的染色法就是，将父节点染为白色，然后将其子节点染为黑色，如果在染色的过程中，出现了，父节点和子节点同为一种颜色的情况，则说明存在奇数环，即不是二分图！

染色的过程既可以使用 dfs 又可以使用 bfs。

860. 染色法判定二分图

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。

输出格式

如果给定图是二分图，则输出 Yes，否则输出 No。

数据范围

1≤n,m≤10⁵

输入样例：

4 4
1 3
1 4
2 3
2 4
1
2
3
4
5

输出样例：

Yes
1

#include
#include
#include
#include
#include
#include
#include
#include
#include

#define x first
#define y second

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;

int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
int lowbit(int x) {return x & -x;}

int n, m;
int h[N], e[N * 2], ne[N * 2], idx;
int color[N];
bool flag;

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

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

int main()
{
	cin >> n >> m;
	memset(h, -1, sizeof h);
	for(int i = 0; i < m; i ++ ){
		int x, y;
		cin >> x >> y;
		add(x, y);
		add(y, x);
	}
	
	for(int i = 1; i <= n; i ++ ){
		if(!color[i]){
			if(!dfs(i, 1)){
				flag = true;
				break;
			}
		}
	}
	
	if(flag) cout << "No" << endl;
	else cout << "Yes" << endl;

	return 0;
}



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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80