bzoj3237(cdq+并查集)

这题一眼lct,然而

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int n,m,k,fa[maxn],sta1[maxn*],sta2[maxn*],top,tt,ans[maxn];
int getfa(int x){
if(x!=fa[x]){
sta1[++top]=x;sta2[top]=fa[x];
fa[x]=getfa(fa[x]);
}
return fa[x];
}
struct edg{
int x,y,tim;
}e[maxn*];
struct que{
int num,c[];
}q[maxn];
void cdq(int l,int r){
int now=top;
if(l==r){
ans[l]=;
for(int i=;i<=q[l].num;++i){
int fx=getfa(e[q[l].c[i]].x);
int fy=getfa(e[q[l].c[i]].y);
if(fx!=fy){
ans[l]=;break;
}
}
while(top!=now)fa[sta1[top]]=sta2[top],top--;
return;
}
++tt;
int mid=l+r>>;
for(int i=l;i<=mid;++i)
for(int j=;j<=q[i].num;++j){
e[q[i].c[j]].tim=tt;
}
for(int i=mid+;i<=r;++i)
for(int j=;j<=q[i].num;++j)
if(e[q[i].c[j]].tim!=tt){
int fx=getfa(e[q[i].c[j]].x);
int fy=getfa(e[q[i].c[j]].y);
if(fx!=fy){
sta1[++top]=fx;sta2[top]=fa[fx];
fa[fx]=fy;
}
}
cdq(l,mid);
while(top!=now){fa[sta1[top]]=sta2[top];top--;}
++tt;
for(int i=mid+;i<=r;++i)
for(int j=;j<=q[i].num;++j){
e[q[i].c[j]].tim=tt;
}
for(int i=l;i<=mid;++i)
for(int j=;j<=q[i].num;++j)
if(e[q[i].c[j]].tim!=tt){//把后面的所有边中前面没删的加上;
int fx=getfa(e[q[i].c[j]].x);
int fy=getfa(e[q[i].c[j]].y);
if(fx!=fy){
sta1[++top]=fx;sta2[top]=fa[fx];
fa[fx]=fy;
}
}
cdq(mid+,r);
}
int main(){
cin>>n>>m;
for(int i=;i<=n;++i)fa[i]=i;
for(int i=;i<=m;++i){
scanf("%d%d",&e[i].x,&e[i].y);
e[i].tim=;
}
cin>>k;tt=;
for(int i=;i<=k;++i){
scanf("%d",&q[i].num);
for(int j=;j<=q[i].num;++j){
scanf("%d",&q[i].c[j]);
e[q[i].c[j]].tim=tt;
}
}
for(int i=;i<=m;++i)
if(e[i].tim!=tt){
int fx=getfa(e[i].x);
int fy=getfa(e[i].y);
if(fx!=fy)fa[fx]=fy;
}
cdq(,k);
for(int i=;i<=k;++i){
if(ans[i])puts("Connected");
else puts("Disconnected");
}
return ;
}

题解说可以cdq+并查集,于是复习了一下cdq;

上一篇:Android 开发笔记 “SharePreference 数据存取”


下一篇:C#中关键字ref与out的区别【转】