参考博客:
Tarjan算法
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
using i64 = long long;
int n,m,s;
vector<int> g[N];
vector<pair<int,int>> q[N];
bool st[N];
int p[N];
int find(int x)
{
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
void add(int a,int b)
{
int aa=find(a);
int bb=find(b);
if(aa!=bb)
p[bb]=a;
return ;
}
int idx;
int ans[N];
void tarjan(int u,int f)
{
st[u]=true;
for(auto v : g[u])
{
if(v==f) continue;
if(!st[v])
{
tarjan(v,u);
p[v]=u;
st[v]=true;
}
}
for(auto w : q[u])
{
int v=w.first;
int id=w.second;
if(st[v])
{
ans[id]=find(v);
}
}
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>s;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
q[a].push_back({b,i});
q[b].push_back({a,i});
}
tarjan(s,0);
for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
}
倍增
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int LOGN = 31;
const int N=5e5+10;
int n,q,s;
int dep[N],par[N][LOGN+1],val[N][LOGN+1];
vector<pair<int,int> > e[N];
void dfs(int u,int f)
{
dep[u] = dep[f] + 1;
for(auto p : e[u])
{
int v=p.first;
if(v==f) continue;
par[v][0]=u;
val[v][0]=p.second;
dfs(v,u);
}
}
//求两个点之间的距离最小值
int query(int u,int v)
{
int ans = 1<<30;
if(dep[u]>dep[v]) swap(u,v);
int d=dep[v]-dep[u];
for(int j=LOGN;j>=0;j--)
{
if(d&(1<<j))
{
ans=min(ans,val[v][j]);
v=par[v][j];
}
}
if(u==v) return ans;
for(int j=LOGN;j>=0;j--) if(par[u][j]!=par[v][j]){
ans=min(ans,min(val[u][j],val[v][j]));
u=par[u][j];
v=par[v][j];
}
ans=min(ans,min(val[u][0],val[v][0]));
return ans;
}
int LCA(int u,int v)
{
if(dep[u]>dep[v]) swap(u,v);
int d=dep[v]-dep[u];
for(int j=LOGN;j>=0;j--)
{
if(d&(1<<j))
{
v=par[v][j];
}
}
if(u==v) return u;
for(int j=LOGN;j>=0;j--) if(par[u][j]!=par[v][j]){
u=par[u][j];
v=par[v][j];
}
return par[u][0];
}
int main()
{
cin>>n>>q>>s;
for(int i=1;i<n; i++)
{
int u,v,w;
cin>>u>>v;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
dfs(s,0);
for(int j = 1;j<=LOGN;j++)
{
for(int u=1;u<=n;u++)
{
par[u][j]=par[par[u][j-1]][j-1];
//val[u][j]=min(val[u][j-1],val[par[u][j-1]][j-1]);
}
}
for(int i=1;i<=q;i++)
{
int u,v;
cin>>u>>v;
cout<<LCA(u,v)<<endl;
}
}
参考题目
P3379 【模板】最近公共祖先(LCA)
P1967 [NOIP2013 提高组] 货车运输