牛客网 二分图判定之交叉染色法

缘起

二分图是图论中一个重要概念. 遂找道题目来学习 牛客网 二分图判定

分析

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
给定一个由n个点，m条边组成的无向图（注意，此图可能不连通），对任意1 ≤ i ≤ m存在一条边连接u[i], v[i]。回答此
图是不是二分图。二分图定义为存在一种给图中每一个点染上黑白两色其中之一的着色方式，使得对每一对有边直接相连的
点颜色不同。 

输入描述:
第一行输入为N和M，代表无向图的点数和边数。
接下来M行，表示M条边，每一行两个整数u[i], v[i]，满足1 ≤ u[i], v[i] ≤ n，保证图中无重边，自环。
其中保证1 ≤ N, M ≤ 100000

输出描述:
一行字符串，为Yes，或者No。
Yes表示输入图是二分图。
No表示输入图不是二分图。

示例1
输入
5 7
1 2
2 3
3 4
4 1
4 5
5 2
输出
Yes

示例2
输入
5 4
1 2
2 3
3 1
4 5
输出
No

【限制】
时间限制：1秒
空间限制：262144K

二分图的判定可以使用交叉染色法. 即从一个点开始，染黑色，然后与它相邻的点染白色，然后继续.

上图1,3,5 染白色, 2和4染黑色, 则就是二分图, 所以上图是一个二分图.

所以使用dfs或者bfs即可.

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
65
66
67
//#include "stdafx.h"

#include <stdio.h>
#include <vector>
using namespace std;
//#define LOCAL

const int maxn = 100005;
int n,m;
vector<int> g[maxn]; //邻接链表法存储图（因为n太大了）
bool visited[maxn],color[maxn];
typedef vector<int>::iterator vit;

bool dfs(int i)
{
	for (vit x = g[i].begin(); x!=g[i].end(); x++)
	{
		if (!visited[*x]) // 如果x尚未访问
		{
			visited[*x] = true;
			color[*x] = !color[i]; // 交叉染色
			if (!dfs(*x))
			{
				return false;
			}
		}
		else if(color[i]==color[*x]) // 如果x已经访问过了并且与i相同颜色
		{
			return false;
		}
	}
	return true;
}

bool sz()
{
	for (int i = 1; i<=n; i++)
	{
		if (!visited[i]) // 因无向图可能不连通
		{
			visited[i] = true;
			if (!dfs(i))
			{
				return false;
			}
		}
	}
	return true;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &m);
	while(m--)
	{
		int u,v;
		scanf("%d%d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u); // 构建无向图
	}
	puts(sz()?"Yes":"No");
	return 0;
}

ac情况

您的代码已保存
答案正确:恭喜！您提交的程序通过了所有的测试用例

bfs做法

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
//#include "stdafx.h"

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
//#define LOCAL

const int maxn = 100005;
int n,m;
vector<int> g[maxn]; //邻接链表法存储图（因为n太大了）
bool visited[maxn],color[maxn];
typedef vector<int>::iterator vit;

bool bfs(int i) // 从i顶点开始bfs
{
	queue<int> q;
	q.push(i);
	while (!q.empty())
	{
		int front = q.front();
		q.pop();
		for (vit x = g[front].begin(); x!=g[front].end(); x++)
		{
			if (!visited[*x])
			{
				visited[*x] = true;
				color[*x] = !color[front];
				q.push(*x);
			}
			else if (color[*x]==color[front])
			{
				return false;
			}
		}
	}
	return true;
}

bool sz()
{
	for (int i = 1; i<=n;i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			if (!bfs(i))
			{
				return false;
			}
		}
	}
	return true;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &m);
	while(m--)
	{
		int u,v;
		scanf("%d%d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u); // 构建无向图
	}
	puts(sz()?"Yes":"No");
	return 0;
}

ac情况

您的代码已保存
答案正确:恭喜！您提交的程序通过了所有的测试用例