学到一个比较好用的套路。用于判断一个连通图删去某个边集之后是否还连通。

先求 \(dfs\) 树,原图不连通当且仅当存在一个树边被删及覆盖它的非树边都被删了。

所以考虑异或,给每个非树边定一个随机权值,把树边的权值定为覆盖它的非树边的权值和。

然后就可以线性基判断是否存在异或和为 \(0\) 的子集了。

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
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int getint(){
char ch=gc(); int res=0,ff=1;
while(!isdigit(ch)) ch=='-'?ff=-1:0, ch=gc();
while(isdigit(ch)) res=(res<<3)+(res<<1)+ch-'0', ch=gc();
return res*ff;
}
const int maxn=100005, maxe=1000005;
int fir[maxn],nxt[maxe],son[maxe],tot=1;
int n,m,Q,w[maxe],b[35],s[maxn],cnt_ans;
bool vis[maxn],used[maxe];
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
inline int getrdm(){
return ((int)rand()<<15)+rand();
}
void dfs1(int x,int e_fa){
vis[x]=true;
for(int j=fir[x];j;j=nxt[j])
if(!used[j>>1]){
used[j>>1]=true;
if(!vis[son[j]]) dfs1(son[j],j); else{
w[j>>1]=getrdm();
s[x]^=w[j>>1]; s[son[j]]^=w[j>>1];
}
}
}
void dfs2(int x,int e_fa){
vis[x]=true;
for(int j=fir[x];j;j=nxt[j])
if(!used[j>>1]){
used[j>>1]=true;
if(!vis[son[j]]) dfs2(son[j],j), s[x]^=s[son[j]];
}
w[e_fa>>1]=s[x];
}
bool Insert(int x){
for(int j=29;j>=0;j--)
if((x>>j)&1){
if(!b[j]){ b[j]=x; return false; }
x^=b[j];
}
return true;
}
int main(){
freopen("bzoj3569.in","r",stdin);
freopen("bzoj3569.out","w",stdout);
srand(2333);
n=getint(); m=getint();
for(int i=1;i<=m;i++){
int x=getint(),y=getint();
add(x,y); add(y,x);
}
dfs1(1,0);
memset(vis,0,sizeof(vis));
memset(used,0,sizeof(used));
dfs2(1,0);
Q=getint();
while(Q--){
memset(b,0,sizeof(b));
int t=getint(),x; int pd=0;
while(t--){
int x=getint()^cnt_ans;
pd|=Insert(w[x]);
}
if(pd) puts("Disconnected");
else cnt_ans++, puts("Connected");
}
return 0;
}