「AHOI2013」连通图

发表于 | 分类于 | | 浏览量： 次

随机？哈希？

传送门

洛谷P5227

BZOJ3237

题解

首先，按照套路，先随便求出原图的一棵生成树。

对于每一条非树边，我们给他随机rand一个随机数作为哈希值。

对于每一条树边，定义它的哈希值为所有覆盖它的非树边的哈希值的异或和。

对于一个边的集合，定义它的哈希值为它所包含的所有边的哈希值的异或和。

对于任意一个给定的删边集合，如果存在一个全部由树边构成的子集的哈希值等于某一个全部由非树边构成的子集的哈希值，那么删了该集合中所有边之后，原图不连通。由于给定的删边集合很小，暴力枚举子集即可。

为了保证正确性，采取双哈希会比较合适。

代码

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
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
const int maxn=100005,maxm=200005;
int n,m,Q,tot,lnk[maxn],son[maxn*2],nxt[maxn*2],id[maxn*2],fa[maxn];
struct FastIO
{
	static const int S=131072;
	char buf[S],*L,*R;int Top;
	~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}
	inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}
	FastIO& operator >> (int& ret)
	{
		ret=0;int f=1;char ch=nc();
		while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
		while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}
		return *this;
	}
	FastIO& operator << (char ch){pc(ch);return *this;}
	FastIO& operator << (const char* S){for(int i=0;S[i];i++) pc(S[i]);return *this;}
}fin,fout;
struct Hash
{
	ULL V1,V2;
	Hash(ULL a=0,ULL b=0):V1(a),V2(b){}
	inline void Init()
	{
		V1=(ULL)rand()*rand()*rand()*rand()*rand();
		V2=(ULL)rand()*rand()*rand()*rand()*rand();
	}
	Hash operator ^ (const Hash& b)const{return (Hash){V1^b.V1,V2^b.V2};}
	bool operator == (const Hash& b)const{return V1==b.V1&&V2==b.V2;}
}F[maxn];
struct Edge{int u,v;bool used;Hash w;}E[maxm];
inline void add_e(int x,int y,int z){tot++;son[tot]=y;id[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;}
inline int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
void Calc(int now,int fa)
{
	for(int i=lnk[now];i;i=nxt[i])
	{
		if(son[i]!=fa)
		{
			Calc(son[i],now);
			F[now]=F[now]^F[son[i]];
			E[id[i]].w=F[son[i]];
		}
	}
}
inline void Build()
{
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		if(getfa(E[i].u)!=getfa(E[i].v))
		{
			fa[fa[E[i].u]]=fa[E[i].v];
			E[i].used=true;
			add_e(E[i].u,E[i].v,i);
			add_e(E[i].v,E[i].u,i);
		}
	}
	for(int i=1;i<=m;i++)
	{
		if(!E[i].used)
		{
			E[i].w.Init();
			F[E[i].u]=F[E[i].u]^E[i].w;
			F[E[i].v]=F[E[i].v]^E[i].w;
		}
	}
	Calc(1,0);
}
int main()
{
	srand(20020222);
	fin>>n>>m;
	for(int i=1;i<=m;i++) fin>>E[i].u>>E[i].v;
	Build();
	fin>>Q;
	while(Q--)
	{
		int c,S[6]={0};bool con=true;
		fin>>c;
		for(int i=1;i<=c;i++) fin>>S[i];
		for(int i=1;i<(1<<c)&&con;i++)
		{
			Hash nw,tw;
			for(int j=1;j<=c;j++)
				if((i&(1<<(j-1)))&&!E[S[j]].used)
					nw=nw^E[S[j]].w;
			for(int j=1;j<=c;j++)
				if((i&(1<<(j-1)))&&E[S[j]].used)
					tw=tw^E[S[j]].w;
			if(nw==tw) con=false;
		}
		fout<<(con?"Connected":"Disconnected")<<'\n';
	}
	return 0;
}