题意：
给定一个
n
n
n 点
m
m
m 条边的无向连通图，其中
1
≤
m
≤
n
+
2
1\leq m\leq n+2
1≤m≤n+2。
m
m
m 条边中有一些条边被染成红色，剩下的边被染成蓝色。只考虑红色边，有
c
1
c_1
c1 个连通分量。只考虑蓝色边，有
c
2
c_2
c2 个连通分量。请你给边进行染色，最小化
c
1
+
c
2
c_1+c_2
c1+c2。
数据范围：
2
≤
n
≤
2
×
1
0
5
,
n
−
1
≤
m
≤
min
(
n
+
2
,
n
×
(
n
−
1
)
2
)
2\leq n\leq 2\times 10^5,n-1\leq m\leq \min(n+2,\frac{n\times(n-1)}{2})
2≤n≤2×105,n−1≤m≤min(n+2,2n×(n−1))
题解：
一开始的思路是，先考虑一棵树，即
m
=
n
−
1
m=n-1
m=n−1 的情况。假设有
k
k
k 条红边，
n
−
1
−
k
n-1-k
n−1−k 条蓝边。
对于
c
1
c_1
c1 ，一条红边相当于缩减一个连通分量
对于
c
2
c_2
c2 ，一条蓝边相当于缩减一个连通分量
可以看成两棵树，一共有
2
n
2n
2n 个连通分量，
c
1
+
c
2
=
2
n
−
k
−
(
n
−
1
−
k
)
=
n
+
1
c_1+c_2=2n-k-(n-1-k)=n+1
c1+c2=2n−k−(n−1−k)=n+1
接下来扩展，
m
=
n
m=n
m=n，此时必然有一个环，但是我们可以将其拆开看。
假设所在环长度为
l
e
n
len
len，颜色都是红色，对于蓝色来说，断掉红色边，就相当于这个环上至少有
l
e
n
len
len 个连通分量，如果将其中一条边修改为蓝色，那么对于红色来说，断掉蓝色边，由于是个环，连通分量数依旧不变，但是对于蓝色来说，断掉红色边，存在两个点是一个连通分量了，总体是减1的。但是如此，继续修改红色边为蓝色边，对于红色的连通分量就要增加1，对于蓝色的连通分量依旧是减少1，所以不变。
故可以得出结论，只要不存在环，就可以使得每条边都可以减少一个连通分量（不论是对于红色还是蓝色来说）
故可以先构造一棵生成树，全为红色。剩下
m
−
n
+
1
m-n+1
m−n+1 条边判断是否会构成环，如果不构成环，全部为蓝色，如果构成环，就把任意一条边染成红色，然后这条边的其中一个点的所有边都染成蓝色，如此，对于蓝色来说就是一条链+两端叶子，对于红色也不会成环了。（注意这里只能把这个边其中一个点对应的所有边都染成蓝色，否则可能会导致蓝色环）
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].emplace_back(v, i);
g[v].emplace_back(u, i);
}
int cycle = -1;
int edge = -1;
vector<int> ans(m);
vector<int> vis(n, 0);
set<int> S;
function<void(int, int)> dfs = [&](int u, int fa) {
vis[u] = 1;
for (auto& [v, idx]: g[u]) {
if (v == fa) continue;
if (vis[v]) {
ans[idx] = 0;
edge = idx;
cycle = v;
S.insert(u);
S.insert(v);
continue;
}
ans[idx] = 1;
dfs(v, u);
}
};
dfs(0, -1);
if (m == n + 2 && S.size() == 3) {
for (auto& [v, idx]: g[cycle]) {
if (edge == idx) ans[idx] = 1;
else ans[idx] = 0;
}
}
for (int u: ans) cout << u;
cout << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
