自动搬运

查看原文

来自洛谷，原作者为

	zlqwq dfs是性价比最高的算法

搬运于2025-08-24 23:02:52，当前版本为作者最后更新于2024-12-11 20:55:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道非常难的板子题。

如果直接在原图上求答案显然很复杂，故可以用 Tarjan 来求出所有的边双连通分量，这样我们就可以在树上利用 lca 求解答案了。

我们发现，当我们在两个连通分量里求答案时，它们之间的边一定要统计，故先 Tarjan，然后求出它们树上的 lca 即可。

代码：

#include<iostream>
#include<vector>
#include<stack>
#include<cmath> 
using namespace std;
const int MAXN=1e5+5;
const int MAXM=2e5+5;
vector<int> z[MAXN];
int u[MAXM],v[MAXM];
int idx,IDX=1,belong[MAXN],c;
int n,m,dfn[MAXN],low[MAXN];
int to[MAXM*4],nxt[MAXM*4],head[MAXM];
int dep[MAXN];
int f[MAXN][21];
stack<int> s; 
void add(int u,int v){
	to[++IDX]=v;
	nxt[IDX]=head[u];
	head[u]=IDX;
}
void tarjan(int u,int lst){
	dfn[u]=low[u]=++idx;
	s.push(u);
	for(int i=head[u];i;i=nxt[i]){
		if(!dfn[to[i]]){
			tarjan(to[i],i);
			low[u]=min(low[to[i]],low[u]);
		}
		else if(i^(lst^1)){
			low[u]=min(low[u],dfn[to[i]]);
		}
	}
	if(dfn[u]==low[u]){
		belong[u]=++c;
		while(s.top()!=u){
			belong[s.top()]=c;
			s.pop();
		}
		s.pop();
	}
}
void init(int u,int fa){
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<=20;++i){
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for(auto v:z[u]){
		if(v^fa){
			init(v,u);
		}
	}
}
int lca(int u,int v){
	if(dep[u]<dep[v]){
		swap(u,v);
	}
	for(int k=20;k>=0;--k){
		if(dep[f[u][k]]>=dep[v]){
			u=f[u][k];
		}
	}
	if(u==v){
		return u;
	}
	for(int k=20;k>=0;--k){
		if(f[u][k]!=f[v][k]){
			u=f[u][k];
			v=f[v][k];
		}
	}
	return f[u][0];
}
int Q;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>u[i]>>v[i];
		add(u[i],v[i]);
		add(v[i],u[i]);
	}
	for(int i=1;i<=n;++i){
		if(!dfn[i]){
			tarjan(i,0);
		}
	}
	for(int i=1;i<=m;++i){
		if(belong[u[i]]^belong[v[i]]){
			z[belong[u[i]]].push_back(belong[v[i]]);
			z[belong[v[i]]].push_back(belong[u[i]]);
		}
	}
	init(1,0);
	cin>>Q;
	while(Q--){
		int u,v;
		cin>>u>>v;
		int LCA=lca(belong[u],belong[v]);
		cout<<dep[belong[u]]+dep[belong[v]]-dep[LCA]-dep[LCA]<<'\n';
	}
	return 0;
}