什么是二分图
二分图又称作二部图，是图论中的一种特殊模型。 设 G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(α,β)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(iinα,jinβ)，则称图G为一个二分图。
二分图是一类特殊的图，它可以被划分为两个部分，每个部分内的点互不相连。下图就是一个典型的二分图。
换成人话的意思就是说：在一个集合内的点不会相连接，只有集合外才有连线
二分图性质
二分图的性质：当且仅当图中不含有奇数环。
（奇数环：环中边的数量是奇数）
证明：
必要性：当有奇数环是必然不是二分图
反证法：假如有奇数环是二分图
如图所示，以上边1开始顺时针标记, 因为是奇数环，很显然不管标记到什么位置，1和4 的颜色都是不同的，但因为是二分图，颜色应该一致，所以矛盾。
充分性：若一个图不含有奇数环，则必是二分图
构造法：构造不含奇数环的图
从图中任意一个点开始遍历，都能确定每一个点的颜色并且不冲突
如何判断是否是二分图？
染色法原理：
这里用1,2表示染上色了，0表示未染色
- 开始对任意一个点染色，标记为1
- 接着判断相邻的顶点是否染色， 未染色则染上与之不同的颜色，记为2
- 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。
给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 u 和 v，表示s点 u 和点 v 之间存在一条边。
输出格式
如果给定图是二分图，则输出 Yes，否则输出 No。
数据范围
1⩽n,m⩽105
输入样例：
输出样例：
代码
dfs版本
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
| #include <iostream>
#include <algorithm>
#include <cstring>
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;
}
|
