算法基础班–第三章–7.1最小生成树—染色法判别二分图
算法模板
模板1:(y总给的模板)
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] == -1) {
if (!dfs(j, !c)) return false;
}
else if (color[j] == c) return false;
}
return true;
}
bool check() {
memset(color, -1, sizeof color);
bool flag = true;
for (int i = 1; i <= n; i++)
if (!color[i] == -1) {
if (!dfs(i, 0)) {
flag = false;
break;
}
}
return flag;
}
模板2:(本题提炼的模板)
int h[N], e[M], ne[M], idx; //用邻接表存图
int color[N];
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 () {
....
....
// 下面是染色过程
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;
}
两种模板的对比:
yxc 模板1代码 color[i] = -1/ 0/ 1 (-1:未染色 0:第一种颜色 1:第二种颜色)
860 模板2代码 color[i] = 0/ 1/ 2 (0:未染色 1:第一种颜色 2:第二种颜色)
yxc 模板1代码 memset(color, -1 sizeof color); 表示所有点初始状态是未染色
860 模板2代码 初始化color[i] = 0; 表示所有点初始状态是未染色
yxc 模板1代码 传的实参是 dfs(i, 0)
860 模板2代码 传的实参是 dfs(i, 1)
均表示枚举每个未被染色点的开始染色颜色是第一种颜色
细节
- 染色失败:相当于至少存在两个相邻点染了相同颜色
- 之所以代码逻辑关系是反着判断return false,是由于 某个点染色成功不代表整个图就是二分图,因此只有某个点染色失败才能break,或,return false;(只有当所有点均不成功时,才能进行判断是否染色 成功)
本题完整代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = 200010; //M是因为无向图的边数是点数的2倍
int n, m;
int h[N], e[M], ne[M], idx; //用邻接表存图
int color[N]; //存当前点的颜色 color[i] = 0, 1 2(0表示未被染色,1表示染上第一种颜色,2表示染上第二种颜色)
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool dfs(int u, int c) { //u表示当前节点,c表示当前点的颜色(c取值 0 1 2只取这3个值)
color[u] = c;
for (int i = h[u]; i != -1; i = ne[i]) { //遍历当前u的邻接点
int j = e[i]; //邻接点的编号用j存
if (!color[j]) { //如果当前点没有染过色的话,则进行染色
if (!dfs(j, 3 - c)) return false; //染成另一种颜色(与u不同的颜色), 如果u是1则j染成2,如果u是2则j染成1,所以用3-c!如果j染色失败则返回false
}
else if (color[j] == c) return false; //如果当前u的邻接点j染过色了,而且和u的颜色相同都是c色,则返回false
}
return true; //表示u号点的所有相邻的点染成了与u不同的颜色,成功染色
}
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); //由于是无向边,add()两次
}
// 下面是染色过程
bool flag = true; //flag用于表示染色的过程中是否有矛盾发生
for (int i = 1; i <= n; i++) //从前往后染,此操作是为了保证每一个点都能够参与染色
if (!color[i]) { //如果当前点没有被染过色,进行染色操作
if (!dfs(i, 1)) { //只要dfs(,)返回的是false,就认为有矛盾发生,令flag = false
flag = false;
break;
}
}
if (flag) puts("Yes"); //flag == true 表示整个染色过程完美进行,说明就是一个二分图
else puts("No"); //否则染色不顺利,有矛盾发生,不是二分图
return 0;
}
bfs实现:
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100011, M = 200011;
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 bfs(int u, int c) {
color[u] = c;
queue<int> q;
q.push(u);
while (!q.empty()) {
int t = q.front(); q.pop();
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (!color[j]) {
color[j] = 3 - color[t];
q.push(j);
}
else if (color[t] == color[j]) return false;
}
}
return true;
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m;
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 (!bfs(i, 1)) {
flag = false;
break;
}
}
if (flag) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}