Description
Input
Output
Sample Input
4 5
1 2
2 3
3 4
4 1
2 4
3
1 5
2 2 3
2 1 2
Sample Output
Connected
Disconnected
Connected
HINT
N<=100000N<=100000 M<=200000M<=200000 K<=100000K<=100000
Source
思路
cdq分治，用并查集维护图，首先将任何询问都没有涉及到的边都添加到并查集中；
对于分治的一个区间的询问：
1. 首先将右区间有左区间没有的边添加到并查集中；
2. 递归处理左区间；
3. 还原并查集到递归这个区间的初始状态；
4. 将左区间有右区间没有的边添加到并查集中；
5. 递归处理右区间；
6. 同3
并查集可以用按秩合并。
代码
#include <cstdio>const int maxn=100000;
const int maxm=1000000;template<typename t>
struct stack
{t s[maxn+10];int head;inline int push(t x){s[++head]=x;return 0;}inline int pop(){--head;return 0; }inline t top(){return s[head];}inline int size(){return head;}
};struct data
{int num,pr,t;
};inline data make_data(int num_,int pr_,int t_)
{data res;res.num=num_;res.pr=pr_;res.t=t_;return res;
}int n,tt;struct union_find_set
{int fa[maxn+10],h[maxn+10],cnt;stack<data> st;inline int find(int x){return fa[x]?find(fa[x]):x;}inline int merge(int x,int y,int kind,int ti){x=find(x);y=find(y);if(x==y){return 1;}--cnt;if(h[x]>h[y]){fa[y]=x;if(kind){st.push(make_data(y,h[x],ti));}}else{fa[x]=y;if(kind){st.push(make_data(x,h[y],ti));}if(h[x]==h[y]){++h[y];}}return 0;}inline int split(int ti){while(st.size()){data d=st.top();if(d.t!=ti){return 0;}st.pop();h[fa[d.num]]=d.pr;fa[d.num]=0;++cnt;}return 0;}
};union_find_set s;
int m,k,c[maxm+10],q[maxm+10][4],line[maxm+10][2],ans[maxm+10];
int tmp[maxm+10];int solve(int l,int r)
{if(l==r){if(s.cnt==1){ans[l]=0;}else{ans[l]=1;}return 0;}++tt;int mid=(l+r)>>1;for(register int i=mid+1; i<=r; ++i){for(register int j=0; j<c[i]; ++j){tmp[q[i][j]]=1;}}for(register int i=l; i<=mid; ++i){for(register int j=0; j<c[i]; ++j){tmp[q[i][j]]=0;}}for(register int i=mid+1; i<=r; ++i){for(register int j=0; j<c[i]; ++j){if(tmp[q[i][j]]==1){s.merge(line[q[i][j]][0],line[q[i][j]][1],1,tt);}}}solve(l,mid);s.split(tt);for(register int i=l; i<=mid; ++i){for(register int j=0; j<c[i]; ++j){tmp[q[i][j]]=1;}}for(register int i=mid+1; i<=r; ++i){for(register int j=0; j<c[i]; ++j){tmp[q[i][j]]=0;}}for(register int i=l; i<=mid; ++i){for(register int j=0; j<c[i]; ++j){if(tmp[q[i][j]]==1){s.merge(line[q[i][j]][0],line[q[i][j]][1],1,tt);}}}solve(mid+1,r);s.split(tt);for(register int i=l; i<=mid; ++i){for(register int j=0; j<c[i]; ++j){tmp[q[i][j]]=0;}}--tt;return 0;
}int main()
{scanf("%d%d",&n,&m);for(register int i=1; i<=m; ++i){scanf("%d%d",&line[i][0],&line[i][1]);}scanf("%d",&k);for(register int i=1; i<=k; ++i){scanf("%d",&c[i]);for(register int j=0; j<c[i]; ++j){scanf("%d",&q[i][j]);}}s.cnt=n;for(register int i=1; i<=n; ++i){s.h[i]=1;}for(register int i=1; i<=k; ++i){for(register int j=0; j<c[i]; ++j){tmp[q[i][j]]=1;}}for(register int i=1; i<=m; ++i){if(!tmp[i]){s.merge(line[i][0],line[i][1],0,0);}}for(register int i=1; i<=k; ++i){for(register int j=0; j<c[i]; ++j){tmp[q[i][j]]=0;}}solve(1,k);for(register int i=1; i<=k; ++i){if(ans[i]){puts("Disconnected");}else{puts("Connected");}}return 0;
}
