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<=100000 M<=200000 K<=100000
自己yy的奇怪解法，首先我们可以发现一张图在联通的时候并查集祖先的$size=n$(这不是废话)
然后就只要线段树分治随便维护一下并查集就完事了
代码：
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<vector>
5 #include<map>
6 #define ls node<<1
7 #define rs node<<1|1
8 #define M 200010
9 #define mod 1000000007
10 using namespace std;
11 struct point{int u,v;}p[M],st[M];
12 int n,m,k,top;
13 int size[M],fa[M],f[M];
14 vector<int>tag[M<<2];
15 int find(int x) {
16 while(x!=fa[x]) x=fa[x];
17 return fa[x];
18 }
19 void insert(int node,int l,int r,int l1,int r1,int id) {
20 if(l1<=l&&r1>=r) {
21 tag[node].push_back(id);return;
22 }int mid=(l+r)/2;
23 if(l1<=mid) insert(ls,l,mid,l1,r1,id);
24 if(r1>mid) insert(rs,mid+1,r,l1,r1,id);
25 }
26 void unionn(int x,int y) {
27 x=find(x),y=find(y);
28 if(x==y) return;
29 if(size[x]<size[y]) swap(x,y);
30 st[++top]=(point){x,y};
31 size[fa[y]=x]+=size[y];
32 }
33 void Del(int now) {
34 while(top!=now) {
35 int x=st[top].u,y=st[top--].v;
36 size[x]-=size[fa[y]=y];
37 }
38 }
39 void Dfs(int node,int l,int r) {
40 int now=top;
41 for(int i=0;i<tag[node].size();i++)
42 unionn(p[tag[node][i]].u,p[tag[node][i]].v);
43 if(l==r) {
44 int x=1;
45 while(fa[x]!=x) x=fa[x];
46 puts(size[x]==n?"Connected":"Disconnected");
47 }
48 else {
49 int mid=(l+r)/2;
50 Dfs(ls,l,mid),Dfs(rs,mid+1,r);
51 }
52 Del(now);
53 }
54 int main() {
55 scanf("%d%d",&n,&m);
56 for(int i=1;i<=n;i++) fa[i]=i,size[i]=1;
57 for(int a,b,i=1;i<=m;i++) {
58 scanf("%d%d",&a,&b);f[i]=1;
59 p[i]=(point){a,b};
60 }
61 scanf("%d",&k);
62 for(int i=1;i<=k;i++) {
63 int c;scanf("%d",&c);
64 for(int j=1;j<=c;j++) {
65 int id;scanf("%d",&id);
66 if(f[id]!=i) insert(1,1,k,f[id],i-1,id);
67 f[id]=i+1;
68 }
69 }
70 for(int i=1;i<=m;i++)
71 if(f[i]!=k+1)
72 insert(1,1,k,f[i],k,i);
73 Dfs(1,1,k);
74 return 0;
75 }