Bzoj3569 DZY Loves Chinese II

, , , ,

Description

给你一个 $n$ 个点 $m$ 条边的无向联通图（无重边、自环）。 有 $q$ 次询问，每次询问给出图上的 $k$ 条边，问删除这 $k$ 条边后图是否仍然联通。

强制在线。

$n,m\le 5\times 10^5,q\le 5\times 10^4,k\le 15$（大概是）

Solution

一般人类智慧。

考虑随便跑出来一个树。所有非树边都是返祖边。

观察到一个图不连通，当且仅当一条树边，满足所有跨过这条树边的非树边都被删了。

维护集合，考虑哈希。给非树边随机赋点权值，树边的权值为所有跨过这条树边的非树边的权值的异或和。

查询的时候不连通的充要条件就是存在一个非空子集异或和为 $0$。线性基搞一下。因为 $k$ 很小，如果多随几次比如开个 bitset 之类的，错误率很小。

感觉错误率大概是 $\dfrac{2^k}{w}$ 左右的。大概就是考虑子集的数量有 $2^k$ 个/

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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 500005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int fa[maxn],n,m,d[maxn];
int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
vector<pair<int,int> >to[maxn];
struct yyy {
	int x,y,w;
}e[maxn];
mt19937 rnd(time(0));
void dfs(int x,int pre) {
	for (auto tmp:to[x]) if (tmp.fi^pre) {
		dfs(tmp.fi,x);
		e[tmp.se].w=d[tmp.fi];
		d[x]^=d[tmp.fi];
	}
}
int c[64];
bool insert(int x) {
	if (!x) return 1;
	int i;
	for (i=32;i>=0;i--) if ((x>>i)&1) {
		if (c[i]) {
			x^=c[i];
			if (!x) return 1; 
		}
		else {c[i]=x;return 0;}
	} 
}
signed main(void){
	freopen("1.in","r",stdin);
	int i,las=0,len,x,y,q;
	read(n);read(m);
	for (i=1;i<=n;i++) fa[i]=i;
	for (i=1;i<=m;i++) {
		read(x),read(y);e[i].x=x,e[i].y=y;
		if (getfa(x)^getfa(y)) {
			to[x].push_back(mk(y,i));
			to[y].push_back(mk(x,i));
			fa[getfa(x)]=getfa(y);
		}
		else {
			e[i].w=rnd();
			d[x]^=e[i].w;
			d[y]^=e[i].w;
		}
	}
	dfs(1,0);
	read(q);
	while (q--) {
		read(len);
		int flag=0;
		memset(c,0,sizeof(c));
		for (i=1;i<=len;i++) {
			read(x);x^=las;
			flag|=insert(e[x].w);
		}
		las+=(flag==0);
		puts(flag==0?"Connected":"Disconnected");
	}
	return 0;
}