CF1680F Lenient Vertex Cover 题解
这道题和「JOISC 2014 Day3」电压非常类似，或者说就是一道题。
题意就是给你一个图，问能否对所有点黑白染色，允许最多一条边的两个顶点都染成黑色。
黑白染色后其实就是一个二分图，那如果有一条边的两个顶点染成黑色，就是说去掉该边后，剩下的图为二分图，注意这里要保证两个顶点的颜色相同，否则无法同时染成黑色。
那么我们考虑线段树分治来做。具体地，对于第 \(i\) 条边，我们让它的存在时间为 \([0, i-1]\) 和 \([i+1, m+1]\)，表示在第 \(i\) 个时刻，只有第 \(i\) 条边没有加上，利用可撤销并查集即可维护是否为二分图。而在 \(m+1\) 时刻，所有边都被加上，用来判断原图是否为二分图。
时间复杂度 \(O(n \log^2 n)\)，时限开得很大，可以过。但是其他方法可以做到线性，我太菜力
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int read() {
int x = 0; char ch = getchar();
while(ch<'0' || ch>'9') ch = getchar();
while(ch>='0'&&ch<='9') x = x*10+(ch-48), ch = getchar();
return x;
}
struct Edge {
int u, v;
} e[N];
int T;
int n, m;
int fa[N<<1], siz[N<<1], top;
struct xwx {
int x, y, del;
}stk[N<<1];
int find(int x) {
if(x == fa[x]) return x;
return find(fa[x]);
}
bool found;
bool vis[N<<1];
struct SegmentTree {
vector<int> tree[N<<2];
#define ls tr<<1
#define rs tr<<1 | 1
void insert(int tr, int L, int R, int lq, int rq, int id) {
if(lq == L && R == rq) {
tree[tr].push_back(id);
return;
}
int mid = (L+R)>>1;
if(lq<=mid) insert(ls, L, mid, lq, min(mid, rq), id);
if(mid < rq) insert(rs, mid+1, R, max(mid+1, lq), rq, id);
}
void init(int tr, int L, int R) {
tree[tr].clear();
if(L == R) {
return;
}
int mid = (L+R)>>1;
init(ls, L, mid);
init(rs, mid+1, R);
}
void solve(int tr, int L, int R, bool flag) {
int now = top;
for(int i:tree[tr]) {
int fx = find(e[i].u), fy = find(e[i].v);
if(fx == fy) {
flag = 0;
} else {
int f2x = find(e[i].u+n), f2y = find(e[i].v+n);
if(fx != f2y) {
if(siz[fx] > siz[f2y]) swap(fx, f2y);
fa[fx] = f2y;
siz[f2y]+=siz[fx];
stk[++top] = (xwx) {fx, f2y, siz[fx]};
}
if(fy != f2x) {
if(siz[fy] > siz[f2x]) swap(fy, f2x);
fa[fy] = f2x;
siz[f2x]+=siz[fy];
stk[++top] = (xwx) {fy, f2x, siz[fy]};
}
}
}
if(L == R) {
if(flag) {
if(L <= m) {
int tx = find(e[L].u), ty = find(e[L].v);
if(tx!=ty) return;//如果去掉一条边，必须保证两个顶点同色。
vis[tx] = 1;//都染成黑色。
vis[ty] = 1;
}
found = 1;
puts("YES");
for(int i = 1; i<=n; ++i) {
int fi = find(i), f2i = find(i+n);
if(!vis[fi] && !vis[f2i]) {
vis[fi] = 1;//如果这个连通块还没有染色，则让初始节点为黑色。
putchar('1');
} else {
putchar('0'+vis[fi]);
}
}
putchar('\n');
return;
}
return;
}
int mid = (L+R)>>1;
solve(ls, L, mid, flag);
if(found) return;
solve(rs, mid+1, R, flag);
if(found) return;
while(top > now) {
xwx tmp = stk[top--];
fa[tmp.x] = tmp.x;
siz[tmp.y]-=tmp.del;
}
}
}seg;
void init() {
for(int i = 1; i<=n*2; ++i) {
fa[i] = i;
siz[i] = 1;
vis[i] = 0;
}
top = 0;
found = 0;
seg.init(1, 1, m+1);
}
int main() {
T = read();
while(T--) {
n = read(), m = read();
init();
for(int i = 1;i<=m; ++i) {
e[i] = (Edge) {read(), read()};
if(i > 1) seg.insert(1, 1, m+1, 1, i-1, i);
if(i <=m) seg.insert(1, 1, m+1, i+1 ,m+1, i);
}
seg.solve(1, 1, m+1, 1);
if(!found) {
puts("NO");
}
}
return 0;
}