LCA

2018-07-26

字数统计: 1.2k字 | 阅读时长: 6min

在这篇博客中，主要讲三种求LCA的方法。

tarjan

#include<bits/stdc++.h>
using namespace std;
int n,q,rt;
template<typename Type>inline void read(Type &xx)
{
    Type f=1;char ch;xx=0;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())xx=xx*10+ch-'0';
    xx*=f;
}
struct node
{
	int ne,to,w;
}ed[1000010];
node e[1000010];
int head[2][500100],cnt,tot;
void add(int u,int v)
{
	ed[++cnt].to=v;
	ed[cnt].ne=head[0][u];
	head[0][u]=cnt;
}
void adde(int u,int v,int w)
{
	e[++tot].to=v;
	e[tot].ne=head[1][u];
	e[tot].w=w;
	head[1][u]=tot;
}
int fa[500100];
int get(int x)
{
	return (fa[x]==x)?x:fa[x]=get(fa[x]);
}
int vis[500100],ans[500100];
void tarjan(int x)
{
	vis[x]=1;
	fa[x]=x;
	for(int i=head[1][x];i;i=e[i].ne)
	{
		int v=e[i].to,w=e[i].w;
		if(vis[v])
			ans[w]=get(v);
	}
	for(int i=head[0][x];i;i=ed[i].ne)
	{
		int v=ed[i].to;
		if(vis[v]) continue;
		tarjan(v);
		fa[v]=x;
	}
}
int main()
{
	read(n),read(q),read(rt);
	for(int i=1;i<n;i++)
	{
		int u,v;
		read(u),read(v);
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=q;i++)
	{
		int u,v;
		read(u),read(v);
		adde(u,v,i);
		adde(v,u,i);
	}
	tarjan(rt);
	for(int i=1;i<=q;i++)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
 }

理解：

tarjan的基本思路基于DFS，是一种离线算法,时间复杂度为Θ（m+q）m边数，q询问数。
从根节点一路走到叶子节点。如果询问（u,v），u为当前节点，vis[v]!=0。
说明已经走过LCA(u,v)。并继续遍历LCA（u,v）的子树。

RMQ

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int ne,to;
}edge[1001000];
int head[500100],cnt,n,q,rt;
void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].ne=head[u];
    head[u]=cnt;
}
int dfn[1001000],first[500100],tot,vis[500100],deep[500100];
inline void dfs(int x)
{
    dfn[++tot]=x;
    first[x]=tot;
    vis[x]=1;
    for(int i=head[x];i;i=edge[i].ne)
    {
        int v=edge[i].to;
        if(vis[v]) continue;
        deep[v]=deep[x]+1;		
        dfs(v);
        dfn[++tot]=x;
    }
}
int dp[100][1000100];
inline void st()
{
    dfs(rt);
    for(int i=1;i<=tot;i++)
        dp[0][i]=dfn[i];
    for(int i=1;(1<<i)<=tot;i++)
    for(int j=1;j+(1<<i)<=tot+1;j++)
    {
        int a=dp[i-1][j],b=dp[i-1][j+(1<<i-1)];
        dp[i][j]=(deep[a]<deep[b])?a:b;
    }
}
inline int RMQ(int a,int b)
{
    int k=log2(b-a+1);
    int x=dp[k][a],y=dp[k][b-(1<<k)+1];
    return deep[x]>deep[y]?y:x;
}
inline int LCA(int u,int v)
{
    int a=first[u],b=first[v];
    if(a>b) swap(a,b);
    printf("%d\n",RMQ(a,b));
}
int main()
{
    scanf("%d%d%d",&n,&q,&rt);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    st();
    for(int i=1;i<=q;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        LCA(u,v);
    }
    return 0;
 }

理解：

RMQ解LCA是在线的算法。先将树预处理出其DFS序，LCA（U,V）一定在dfs序u和v之间。
用RMQ预处理出每段区间中深度最小的点就是他的LCA。

倍增法

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int to,ne;
}edge[1000010];
int head[500010],cnt,n,rt,q;
void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].ne=head[u];
    head[u]=cnt; 
}
int fa[20][500001],dis[500010];
inline void dfs(int u)
{
	for(int i=head[u];i;i=edge[i].ne)
	{
		int v=edge[i].to;
		if(v==fa[0][u]) continue;
		dis[v]=dis[u]+1;
		fa[0][v]=u;
		dfs(v);
	}
}
inline void init()
{
	dfs(rt);
	for(int i=1;(1<<i)<=n;i++)
	for(int j=1;j<=n;j++)
	fa[i][j]=fa[i-1][fa[i-1][j]];
} 
inline void LCA(int a,int b)
{
	if(dis[a]>dis[b]) swap(a,b);
	int c=dis[b]-dis[a];
	for(int i=0;(1<<i)<=c;i++)//i从0开始 
	{
		if((1<<i)&c) b=fa[i][b];
	}
	if(a!=b)
	{
		for(int i=(int)log2(n);i>=0;i--)
		if(fa[i][a]!=fa[i][b]) a=fa[i][a],b=fa[i][b];
		a=fa[0][a];
	}
	printf("%d\n",a);
}
int main()
{
	memset(dis,0,sizeof(dis));
	scanf("%d%d%d",&n,&q,&rt);
	for(int i=1;i<=n;i++) fa[0][i]=i;
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		add(u,v);
		add(v,u);
	}
	init();
	for(int i=1;i<=q;i++)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		LCA(u,v);
	}
	return 0;
}

理解：

一遍dfs处理出每个点的父亲。然后预处理出每个点往上跳2^i个点的父亲。
开始LCA时，先把两个点的深度跳到一样。然后从大到小（2^n~2^0）跳，如果fa[i][a]==fa[i][b]说明跳过了，不更新b，a，最后fa[0][a]就是他们的LCA。

提醒：

遇到大数据，输入输出一定要用scanf()和printf()。把cout换为printf()快了将近2000ms。

本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/5c4ec076.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！