Category: 整体二分

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3237

解题报告

这个题目，真心没辙
最开始想，我们可以搞一个像Sparse_Table一样的玩意，然后用O(n)的时间单次合并并查集
然而这样的复杂度最后算下来和暴力没差多少QAQ
所以看了题解，写了网上提到的分治算法
感觉好神！
不是整体二分，也不是CDQ，就是分治，但好神！
赶紧Mark

Code

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 100000+9;
const int M = 1000000+9; 
const int SGZ = 5;

int u[M],v[M],is_del[M],vout[N],idx;
int fa[N],n,m,k,sz[N],edg[N][SGZ];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

namespace Union_Find_Set{
	#define UFS Union_Find_Set
	int t1[M*5],t2[M*5],cnt;
	
	inline int find(int w){
		int f = fa[w], tmp;
		while (fa[f] != f) f = fa[f];
		while (w != f) t1[++cnt] = w, t2[cnt] = fa[w], fa[w] = f, w = t2[cnt];
		return f; 
	}
	
	inline void Union(int a, int b) {
		int f1 = find(a), f2 = find(b); 
		if (f1 != f2) ++cnt, fa[t1[cnt]=t2[cnt]=f1] = f2; 
	}
	
	inline void reset(int Tag) {
		for (;cnt>Tag;cnt--) 
			fa[t1[cnt]] = t2[cnt];
	}
};

void solve(int l, int r){
	int cur_time = UFS::cnt; 
	if (l == r) {
		vout[l] = 1; 
		for (int i=1,w;i<=sz[l] && vout[l];i++) { 
			w = edg[l][i];
			if (UFS::find(u[w]) != UFS::find(v[w])) vout[l] = 0;
		} 
		UFS::reset(cur_time);
	} else {
		int mid = l + r + 1 >> 1; ++idx; 
		for (int i=mid;i<=r;i++) for (int j=1;j<=sz[i];j++) is_del[edg[i][j]] = idx;
		for (int i=l;i<mid;i++) for (int j=1,w;j<=sz[i];j++) {
			w = edg[i][j];
			if (is_del[w] != idx) UFS::Union(u[w],v[w]);
		}
		solve(mid,r);
		UFS::reset(cur_time); ++idx;
		for (int i=l;i<mid;i++) for (int j=1;j<=sz[i];j++) is_del[edg[i][j]] = idx;
		for (int i=mid;i<=r;i++) for (int j=1,w;j<=sz[i];j++) {
			w = edg[i][j];
			if (is_del[w] != idx) UFS::Union(u[w],v[w]);
		}
		solve(l,mid-1);
		UFS::reset(cur_time);
	}
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=n;i++) fa[i] = i;
	for (int i=1;i<=m;i++) u[i] = read(), v[i] = read();
	k = read();
	for (int i=1;i<=k;i++) {
		sz[i] = read();
		for (int j=sz[i];j;--j) 
			is_del[edg[i][j] = read()] =-1;
	} 
	for (int i=1;i<=m;i++) if (~is_del[i]) UFS::Union(u[i],v[i]);
	solve(1,k);
	for (int i=1;i<=k;i++) puts(vout[i]?"Connected":"Disconnected");
	return 0; 
}

感觉并查集撤销那里，应该用持久化并查集才对吧
感觉用栈的话，时间复杂度不对啊

另外，看看Memphis不到1s的算法，应该是有什么奇技淫巧
但找不到任何相关资料QAQ

—————————— UPD 2017.2.1 ——————————
这题还可以用线性基搞一搞
另外，并查集撤销那里没问题，不需要可持久化