下面用 \(G\) 表示一个环的边集，记作环 \(G\)。
我们令一个环 \(G\) 的价值为它经过的返祖边数量，记作 \(Z(G)\)，下面给出核心结论：
若存在一条边 \(e_0\) 经过所有 \(Z(G) = 1\) 的奇环，且不经过任意一个 \(Z(G) = 1\) 的偶环，那么 \(e_0\) 经过所有奇环，且不经过任意一个偶环
下面给出简单的证明：
定义两个环的异或值 \(G = G_1 \otimes G_2\) 满足：
该运算显然满足交换律和结合律。
引理：对于任意环 \(G\)，均可以被唯一分解为 \(G = G_1 \otimes G_2 \dots \otimes G_m\)，其中 \(Z(G) = m\)，满足 \(\forall 1 \le i \le m\)，都有 \(Z(G_i) = 1\)。
证明：考虑数学归纳法，当 \(m = 1\) 时显然成立。下面假定当 \(m = k\) 时成立，则当 \(m = k + 1\) 时，容易发现 \(G_{k + 1}\) 和 \(G \otimes G_1 \otimes G_2 \dots \otimes G_k\) 显然相等，若不等，则通过 \(G_1, G_2, \dots, G_{k + 1}\) 中的返祖边显然不能成环，与环 \(G\) 矛盾。（具体的严谨证明笔者也不太会，只能感性理解）
若对于一个环 \(G = G_1 \otimes G_2 \dots \otimes G_m\)，容易发现原环上的边由所有小环的边之和减去重合的边，即 \(|G| = \sum\limits_{i = 1}^{m} |G_i| - \Delta\)， 且 \(2 \mid \Delta\)，那么环 \(G\) 的奇偶性只和 \(G_1, G_2 \dots G_m\) 中的奇环数目 \(x\) 有关，具体的：
-
若 \(2 \mid x\)，那么环 \(G\) 为偶环，若存在一条边 \(e_0\) 经过所有的奇环，那么 \(e_0\) 必然不经过 \(G\)。
-
若 \(2 \nmid x\)，那么环 \(G\) 为奇环，若存在一条边 \(e_0\) 经过所有的奇环，那么 \(e_0\) 必然经过 \(G\)。
综上所述，原结论显然成立。
接下来的处理就很简单，只需要用树上差分统计每条边经过几个奇环和偶环，最后寻找是否存在一条 \(e_0 = (u_0, v_0)\) 满足经过所有奇环，且不经过一个偶环的边。
输出方案的话，若原图为二分图，直接染色即可，否则删掉 \(e_0\) 后，钦定 \(col_{u_0} = 1\) 染色即可，注意多测要清空。
时间复杂度为 \(\mathcal{O}(n + m)\)
代码
#include<bits/stdc++.h>
#define MULT_TEST 1
using namespace std;
inline int read() {
int w = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
w = (w << 1) + (w << 3) + ch - 48;
ch = getchar();
}
return w * f;
}
inline void Solve() {
int n, m, sum = 0, t = 0, opt = -1;
n = read(); m = read();
vector<int> dep(n + 1), ans(n + 1), vis(n + 1), tag(n + 1), h(m + 1);
vector<vector<pair<int, int>>> e(n + 1), E(n + 1);
for (int i = 1; i <= m; i++) {
int u = read(), v = read();
e[u].push_back({v, i});
e[v].push_back({u, i});
}
function<void(int, int)> DFS1 = [&](int x, int fa) {
vis[x] = 1;
dep[x] = dep[fa] + 1;
for (auto [u, id] : e[x]) {
if (u == fa) continue;
if (vis[u]) {
if (dep[u] > dep[x]) continue;
if ((dep[x] - dep[u]) & 1) tag[u]++, tag[x]--, h[id]--;
else sum++, tag[u]--, tag[x]++, h[id]++;
}
else {
E[x].push_back({u, id});
DFS1(u, x);
}
}
};
function<void(int, int)> DFS2 = [&](int x, int id2) {
for (auto [u, id] : E[x]) {
DFS2(u, id);
tag[x] += tag[u];
}
if (id2 > 0) h[id2] = tag[x];
};
bool flag = 1;
function<void(int, int)> DFS3 = [&](int x, int col) {
vis[x] = 1;
ans[x] = col;
for (auto [u, id] : e[x]) {
if (vis[u]) {
if (ans[u] == col) flag = 0;
continue;
}
if (id == opt) continue;
DFS3(u, col ^ 1);
}
};
DFS3(1, 1);
if (flag) {
printf("YES\n");
for (int i = 1; i <= n; i++) printf("%d", ans[i]);
puts("");
return ;
}
vis.clear(); vis.resize(n + 1);
DFS1(1, 1); DFS2(1, -1);
for (int i = 1; i <= n; i++)
for (auto [u, id] : e[i])
if (h[id] == sum) opt = id, t = i;
if (opt == -1) printf("NO\n");
else {
vis.clear(); vis.resize(n + 1);
DFS3(1, 1);
printf("YES\n");
for (int i = 1; i <= n; i++) printf("%d", ans[i] ^ (ans[t] == 0));
puts("");
}
}
signed main() {
int T = 1;
#if MULT_TEST
T = read();
#endif
while (T--) Solve();
return 0;
}