1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| #include<bits/stdc++.h>
using namespace std;
#define N 200010
struct DSU
{
int fa[N],rk[N],cnt;
pair<int*,int> stk[N<<3];
int siz;
void init(int n)
{
cnt=n;siz=0;
for(int i=1;i<=n;++i)
fa[i]=i,rk[i]=0;
}
int Find(int x)
{
while(x!=fa[x]) x=fa[x];
return x;
}
bool Union(int x,int y)
{
x=Find(x);y=Find(y);
if(x==y) return false;
if(rk[x]<rk[y]) swap(x,y);
stk[++siz]=pair<int*,int>(fa+y,fa[y]);
fa[y]=x;
if(rk[x]==rk[y])
{
stk[++siz]=pair<int*,int>(rk+x,rk[x]);
++rk[x];
}
stk[++siz]=pair<int*,int>(&cnt,cnt);
--cnt;
return true;
}
void Undo(int tim)
{
while(siz>tim)
{
*stk[siz].first=stk[siz].second;
--siz;
}
}
} dsu;
struct edge
{
int x,y;
} e[N];
int n,m,q;
bool vis[N],ans[N];
struct node
{
int c,a[4];
} t[N];
void setvis(int l,int r,bool flag)
{
for(int i=l;i<=r;++i)
for(int j=0;j<t[i].c;++j)
vis[t[i].a[j]]=flag;
}
void add(int l,int r)
{
for(int i=l;i<=r;++i)
for(int j=0;j<t[i].c;++j)
{
int o=t[i].a[j];
if(!vis[o])
dsu.Union(e[o].x,e[o].y);
}
}
void solve(int l,int r)
{
if(l==r)
{
ans[l]=(dsu.cnt==1);
return;
}
int mid=l+r>>1,now=dsu.siz;
setvis(l,mid,1);
add(mid+1,r);
setvis(l,mid,0);
solve(l,mid);
dsu.Undo(now);
setvis(mid+1,r,1);
add(l,mid);
setvis(mid+1,r,0);
solve(mid+1,r);
dsu.Undo(now);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
scanf("%d%d",&e[i].x,&e[i].y);
scanf("%d",&q);
for(int i=1;i<=q;++i)
{
scanf("%d",&t[i].c);
for(int j=0;j<t[i].c;++j)
{
scanf("%d",&t[i].a[j]);
vis[t[i].a[j]]=true;
}
}
dsu.init(n);
for(int i=1;i<=m;++i)
if(!vis[i]) dsu.Union(e[i].x,e[i].y);
else vis[i]=false;
solve(1,q);
for(int i=1;i<=q;++i)
puts(ans[i]?"Connected":"Disconnected");
return 0;
}
|