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;
}