P11022 「LAOI-6」Yet Another Graph Coloration Problem - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
关于无解情况，如果这个图有两块连通块，那么不可能同时有黑色白色，假设 \(1,2\) 连通块，设 \(1\) 中有黑色，因为 \(2\) 中点不能到 \(1\)，所以 \(2\) 中只能是黑色，又因为 \(2\) 中都是黑色，\(1\) 中点不能到 \(2\)，所以 \(1\) 中点都是黑色，所以一个图全是黑色。 所以只能是一整块连通图。
先考虑贪心，先把所有点变成白色，看看那些点能变为黑色。
容易发现，对于一个无出边的环，可以随便选黑色，但如果有出边，即有桥的话，桥相连点只能是同色，可以发现只要有环，那么就可以选出来两种颜色，即一定有解。而如果这张图没有环，即是一个树，那么两点不可能存在多个简单路径，因此无解。
所以，我们可以先给桥边点标记。然后从点 1 开始染黑色，并把和点 1 相连的，非同一双连通分量（即环）里的桥点也染成黑色即可。
此题结束。
注意，对于大测试量，不要循环 memset 容易爆，要采用循环清空。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;const int N = 200010, M = N * 2;int h[N], ne[M], e[M], idx;
int n, m;
int dfn[N], timestamp, dcc_cnt, low[N];
int stk[N], top, id[N];
bool st[N], flag1;
bool B[N];
vector<int> g[N];void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}void tarjan(int u, int from)
{dfn[u] = low[u] = ++ timestamp;stk[ ++ top] = u;for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (!dfn[j]){tarjan(j, i);low[u] = min(low[u], low[j]);if (dfn[u] < low[j]){st[u] = st[j] = true;}}else if (i != (from ^ 1)){low[u] = min(low[u], dfn[j]);}}if (dfn[u] == low[u]){int y;dcc_cnt ++ ;do {y = stk[top -- ];id[y] = dcc_cnt;g[dcc_cnt].push_back(y);}while (y != u);if (g[dcc_cnt].size() >= 3) flag1 = true; // 说明有环}
}void dfs(int u)
{B[u] = 1;for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (st[j] && id[u] != id[j] && !B[j])dfs(j);}
}int main()
{ int T;cin >> T;while (T -- ){cin >> n >> m;for (int i = 1; i <= n; i ++ ){st[i] = 0;dfn[i] = 0;h[i] = -1;top = 0;g[i].clear();B[i] = 0;}idx = dcc_cnt = 0;flag1 = 0;timestamp = 0;while (m -- ){int a, b;scanf("%d%d", &a, &b);add(a, b);add(b, a);}int cnt = 0;for (int i = 1; i <= n; i ++ )if (!dfn[i]){tarjan(i, -1);cnt ++ ; }if (cnt > 1){puts("-1");continue;}if (flag1) {dfs(1);for (int i = 1; i <= n; i ++ ){if (B[i]) putchar('B');else putchar('W');}}else {puts("-1");continue;}puts("");}return 0;}
