给构造题提供了一种新的思路。
如果答案占总方案数的比较大，可以考虑随机化。
例如本题，考虑随机化，难点变成判断一个方案是否可行。考虑 2-SAT，如果一个点是 \(\text{B}\)，那么对于这个点的边，有一条边的另一个端点是 \(\text{W}\)，那么其他两个都是 \(\text{B}\)。反之同理。跑一遍 2-SAT 即可知道随出来的这个解是否合法。
code
// Problem: E - Not Dyed by Majority (Cubic Graph)
// Contest: AtCoder - AtCoder Regular Contest 161
// URL: https://atcoder.jp/contests/arc161/tasks/arc161_e
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 500100;
int n, f[maxn], head[maxn], len;
vector<int> G[maxn];
mt19937 rnd(time(NULL));
int dfn[maxn], low[maxn], times, scc[maxn], cnt, stk[maxn], top;
struct edge {
int to, next;
} edges[maxn * 10];
inline void add_edge(int u, int v) {
edges[++len].to = v;
edges[len].next = head[u];
head[u] = len;
}
void dfs(int u) {
dfn[u] = low[u] = ++times;
stk[++top] = u;
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if (!dfn[v]) {
dfs(v);
low[u] = min(low[u], low[v]);
} else if (!scc[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
++cnt;
while (1) {
int x = stk[top--];
scc[x] = cnt;
if (x == u) {
break;
}
}
}
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
vector<int>().swap(G[i]);
}
for (int i = 0, u, v; i < n * 3 / 2; ++i) {
scanf("%d%d", &u, &v);
G[u].pb(v);
G[v].pb(u);
}
while (1) {
for (int i = 1; i <= n; ++i) {
f[i] = rnd() & 1;
}
len = times = cnt = 0;
for (int i = 1; i <= n * 2; ++i) {
head[i] = dfn[i] = low[i] = scc[i] = 0;
}
for (int i = 1; i <= n; ++i) {
int u = G[i][0], v = G[i][1], w = G[i][2];
if (f[i]) {
add_edge(u, v + n);
add_edge(u, w + n);
add_edge(v, u + n);
add_edge(v, w + n);
add_edge(w, u + n);
add_edge(w, v + n);
} else {
add_edge(u + n, v);
add_edge(u + n, w);
add_edge(v + n, u);
add_edge(v + n, w);
add_edge(w + n, u);
add_edge(w + n, v);
}
}
for (int i = 1; i <= n * 2; ++i) {
if (!dfn[i]) {
dfs(i);
}
}
bool flag = 0;
for (int i = 1; i <= n; ++i) {
if (scc[i] == scc[i + n]) {
for (int u = 1; u <= n; ++u) {
putchar(f[u] ? 'B' : 'W');
}
putchar('\n');
flag = 1;
break;
}
}
if (flag) {
break;
}
}
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}