题目描述
给一个允许有重边和自环的无向图，你需要将每条边染色成红色或蓝色，使得所有度数 的点，都既与一条蓝色边相连，又与一条红色边相连。问是否有解，有解的话输出一组解。
题解
随便找一个点, dfs
无向图 dfs 只有树边和返祖边
树边:
每一层不一样, 根节点...
返祖边:
- 连接的一个顶点为非叶、根节点: 满足另外一个点的
- 连接叶子与根节点
1. 需要同一个颜色: 满足
2. 非1 满足根, 叶节点往上找到第一个度数 >= 3 的点, 反转这些点的颜色
如果到了根节点都不满足, 无解!
点击查看代码
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define RED ((false))
#define BLACK ((true))
using namespace std;
const int N = 1e5 + 5, M = 6e5 + 5;
int n, m;
int h[N], e[M], nxt[M], idx;
bool col[M]; // 边的颜色
bool colour[N]; // 点的颜色 (需要的颜色)
bool vis[M]; // 边是否用过
int father[N]; // 到父节点的边
int d[N]; // 度数
bool root_is_first; // 是否第一次遍历到根
bool root_has_two_col; // 根是否有两个颜色
int root; // 根
bool st[N]; // 点是否用过
void add(int a, int b) {
e[idx] = b, nxt[idx] = h[a], h[a] = idx ++;
}
// 节点, 该染的颜色
void dfs(int u, int color) {
st[u] = true; // 已遍历
colour[u] = color; // 染色
for(int i = h[u]; ~i; i = nxt[i]) {
int v = e[i];
if(u == root && !root_has_two_col && !vis[i]) {
// 这个点是根节点, 没有两个颜色, 没有遍历过这条边
if(root_is_first) {
root_is_first = false;
// color 为 RED
} else {
root_has_two_col = true; // 有两个颜色
color = !color; // 第二个颜色
}
}
if(!st[v]) { // 没遍历过
col[i] = col[i ^ 1] = !color; // 下一个颜色
vis[i ^ 1] = true; // 标记反向边
father[v] = i;
dfs(v, !color); // 遍历
} else if(!vis[i]) { // 返祖边
vis[i ^ 1] = true; // 标记反向边
// 要同一个颜色 或 随便染色
if(color != colour[v] || v != root || root_has_two_col) {
col[i] = col[i ^ 1] = !color; // 染色
if(v == root) root_has_two_col = true; // 有两个颜色了
} else { // 与根节点冲突
int cur = i; // 当前这个边
int c = color; // 现在的颜色
while(cur) {
col[cur] = col[cur ^ 1] = c; // 反色
if(d[e[cur ^ 1]] >= 3) break;
cur = father[e[cur ^ 1]], c = !c; // 往父亲节点走
}
if(cur) root_has_two_col = true; // 根节点有两个颜色了
}
}
}
}
int main() {
int T;
scanf("%d", &T);
while(T --) {
memset(h, -1, sizeof(h));
memset(d, 0, sizeof(d));
memset(col, false, sizeof(col));
memset(vis, false, sizeof(vis));
memset(st, false, sizeof(st));
memset(colour, false, sizeof(colour));
idx = 0;
scanf("%d%d", &n, &m);
for(int i = 1, a, b; i <= m; i ++) {
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
d[a] ++, d[b] ++;
}
bool die = false;
for(int i = 1; i <= n; i ++)
if(!st[i]) {
root_is_first = true;
root_has_two_col = false;
root = i;
dfs(i, RED);
// 根节点的度数为 2 且 根节点没有两个颜色 -> 无解
if(!root_has_two_col && d[root] == 2) {
die = true;
break;
}
}
if(die) {
puts("No solution.");
} else {
for(int i = 0; i < m; i ++) {
putchar(col[i << 1] ? 'B' : 'R');
}
putchar(10);
}
}
return 0;
}