传送门
cdq分治好题。
对于一条边，如果加上它刚好连通的话，那么删掉它会有两个大集合A,B。于是我们先将B中禁用的边连上，把A中禁用的边禁用，再递归处理A；然后把A中禁用的边连上，把B中禁用的边禁用。
这样递归下去用并查集维护答案就行了。
另外，当向上回溯时需要撤销之前的操作，因此需要用栈维护并查集历史信息。
代码：
#include<bits/stdc++.h>
#define N 100005
#define M 200005
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int tot=0,n,m,k,fa[N],ans[N];
bool ban[M];
struct edge{int u,v;}tt[M],q[M*50];
vector<int>del[N];
inline int find(int x){
if(x!=fa[x])q[++tot]=(edge){x,fa[x]},fa[x]=find(fa[x]);
return fa[x];
}
inline void merge(int u,int v){
int fx=find(u),fy=find(v);
if(fx!=fy)q[++tot]=(edge){fy,fa[fy]},fa[fy]=fx;
}
inline void rec(int l,int r,int tmp){for(int i=l;i<=r;++i)for(int j=0;j<del[i].size();++j)ban[del[i][j]]=tmp;}
inline void add(int l,int r){
for(int i=l;i<=r;++i)for(int j=0;j<del[i].size();++j){
int pos=del[i][j];
if(ban[pos])continue;
merge(tt[pos].u,tt[pos].v);
}
}
inline void clear(int tim){while(tot>tim)fa[q[tot].u]=q[tot].v,--tot;}
inline bool check(int p){
for(int i=0;i<del[p].size();++i){
int fx=find(tt[del[p][i]].u),fy=find(tt[del[p][i]].v);
if(fx!=fy)return 0;
}
return 1;
}
inline void solve(int l,int r){
if(l==r){ans[l]=check(l);return;}
int mid=l+r>>1;
int cnt=tot;
rec(l,mid,1),add(mid+1,r),rec(l,mid,0),solve(l,mid);
clear(cnt);
rec(mid+1,r,1),add(l,mid),rec(mid+1,r,0),solve(mid+1,r);
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i)fa[i]=i;
for(int i=1;i<=m;++i)tt[i].u=read(),tt[i].v=read();
k=read();
for(int i=1;i<=k;++i){
int c=read();
for(int j=1;j<=c;++j){
int tmp=read();
del[i].push_back(tmp);
}
}
rec(1,k,1);
for(int i=1;i<=m;++i)if(!ban[i])merge(tt[i].u,tt[i].v);
rec(1,k,0),tot=0,solve(1,k);
for(int i=1;i<=k;++i)puts(ans[i]?"Connected":"Disconnected");
return 0;
}