相关链接
题目传送门: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 ——————————
这题还可以用线性基搞一搞
另外,并查集撤销那里没问题,不需要可持久化