#C241127B. [AHOI2013] 连通图

标签（Label）

dfs搜索树
哈希
lca

网址（Website）

题目详情 - 切割「GDKOI2024普及组」 - Super

P5227 [AHOI2013] 连通图 - 洛谷

题目（Problem）

题目描述

给定一个无向连通图和若干个小集合，每个小集合包含一些边，对于每个集合，你需要确定将集合中的边删掉后改图是否保持联通。集合间的询问相互独立

定义一个图为联通的当且仅当对于任意的两个顶点，都存在一条路径连接它们

输入格式

第一行为两个整数 $n,m$，代表无向图的点数和边数

下面 $m$ 行，包含两个整数 $u,v$，代表该边连接点 $u,v$。第 $i + 1$ 行的边的编号为 $i$。保证不存在重边和自环

下面一行包含一个整数 $k$，表示集合个数

下面 $k$ 行每行描述一个集合，每行的第一个数为集合中边的个数 $c$，后面 $c$ 个数代表集合内的边

输出格式

对于每个集合，输出一行代表去掉该集合中的边后图是否联通，如果联通输出 Connected，否则输出 Disconnected

样例 #1

样例输入 #1

样例输出 #1

Connected
Disconnected
Connected

提示

$1~~\leq~~n,k~~\leq~~10^5$

$1~~\leq~~m~~\leq~~2~~\times~~10^5$

$1~~\leq~~c~~\leq~~4$

题解（Solution）

很好的一个想法，由于要判断连通性，先考虑转成树论来做，因此先建立一棵 $\text{dfs}$ 搜索树，这时所有的非树边一定都是返祖边，我们考虑计算每次删边之后的影响，由于树连通了所有点，所以删边的时候一定要删掉至少一条树边，那么我们考虑删了树边之后如何处理非树边的影响，发现非树边所连接的两端会使这两个端点组成的树链保持连接，因此，如果断掉树上这条链上的边，就必须断掉这条返祖边，容易发现这条返祖边对树上边的贡献就是这条路径，容易想到使用树上差分来处理，但是，每条边都是不同的，我们如何区分不同的边呢？这其实我们使用类似 $\text{Hash}$ 的想法，给每条非树边随机附一个权值，并且给树上的边异或上这个权值，代表这条树边会受这条非树边的影响。

接下来就需要考虑什么情况下图才会分成两部分，有几种情况：

断掉一条树边，以及能影响到这条边的非树边。此时这条树边的权值为 $0$ ，且会被删去。
断掉两条树边，此时两条树边中间部分被断开。此时这两条树边的权值相等，且都会被删去。

在询问的处理每个询问就好了，时间复杂度 $O(n\log n+q\times c^2)$ 。

莫名其妙，建 $\text{dfs}$ 搜索树的时候访问边的顺序不同会导致答案正确性不同，想不通。我和同机房的巨佬一个用的链式前向星，一个用的邻接表，就因为一个是正着搜，一个倒着搜，都是 $\text{95pts}$ ，错的点甚至不一样，后面就想到了使用 $\texttt{shuffle}$ 函数随机一个顺序，靠阳寿 $\text{AC}$ 了这道题。。。

正确性不对吗？很奇怪。

代码（Code）

100分

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a,b) {For(i,1,b) cerr<<a[i]<<' ';cerr<<'\n';}
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar(x+'0');
	else write(x/10), putchar(x%10+'0');
}constexpr int inf = 0x3f3f3f3f3f3f3f3f;
constexpr int N = 2012345;
bool ST;mt19937_64 rr(time(0));
int rnd(int l,int r){return rr()%(r-l+1)+l;}

vector<P> ft[N];
P p[N];
int n,m; 

bitset<N> vst,intree;
int f[N][24],dfn[N],idx;
int dep[N];
void dfs_tree(int x,int fa){
	f[dfn[x]=++idx][0]=fa, dep[x]=dep[fa]+1;
	vst[x] = true;
	shuffle(ft[x].begin(),ft[x].end(),rr);
	for(auto p:ft[x]){
		int y,id;tie(y,id)=p;
		if(vst[y]) continue;
		intree[id] = true;
		dfs_tree(y,x);
	}
}


inline int cmn(int x,int y){return dfn[x]<dfn[y]?x:y;}
inline int lca(int x,int y){
	if(x==y) return x;
	if((x=dfn[x])>(y=dfn[y])) swap(x,y);
	int d = __lg(y-x++);
	return cmn(f[x][d], f[y-(1<<d)+1][d]);
}

int ve[N], vd[N];
void dfs_sub(int x,int fa){
	for(auto p:ft[x]){
		int y,id;tie(y,id)=p;
		if(y^fa && intree[id])
			dfs_sub(y,x), vd[x] ^= vd[y];
	}
}

void Solve(){
	n=rd(),m=rd();For(i,1,m){p[i]={rd(),rd()};
		ft[p[i].x].emplace_back(p[i].y,i);
		ft[p[i].y].emplace_back(p[i].x,i);
	}dfs_tree(1,0);
	For(j,1,__lg(n)) for(int i=1;i+(1<<j)-1<=n;i++)
		f[i][j] = cmn(f[i][j-1], f[i+(1<<(j-1))][j-1]);
	
	For(i,1,m) if(!intree[i]){
		ve[i] = rr();
		int x,y;tie(x,y)=p[i];
		vd[x] = vd[x] ^ ve[i];
		vd[y] = vd[y] ^ ve[i];
	}dfs_sub(1,0);
	
	For(i,1,m) if(dep[p[i].x] < dep[p[i].y]) swap(p[i].x,p[i].y);
	
	int q=rd();while(q--){
		int k=rd(),flag=1;vector<int> e1,e2;
		For(i,1,k){int id=rd();intree[id] ? e1.emplace_back(id) : e2.emplace_back(id);}
		
		for(auto i:e2){
			int x=p[i].x,y=p[i].y;
			for(auto j:e1){
				int u=p[j].x,v=p[j].y;
				if(lca(u,x)==u && lca(v,y)==y){
					vd[u] = vd[u] ^ ve[i];
				}
			}
		}
		for(auto i:e1) for(auto j:e1) if(flag && i^j){
			if(vd[p[i].x]==vd[p[j].x]) puts("Disconnected"), flag=0;}
		for(auto i:e1) if(flag && vd[p[i].x]==0) puts("Disconnected"), flag=0;
		if(flag) puts("Connected");
		
		//还原修改 
		for(auto i:e2){
			int x=p[i].x,y=p[i].y;
			for(auto j:e1){
				int u=p[j].x,v=p[j].y;
				if(lca(u,x)==u && lca(v,y)==y){
					vd[u] = vd[u] ^ ve[i];
				}
			}
		}
	}
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1;double Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}