最近公共祖先LCA模板

概述

求最近公共祖先一共有3种算法:

  • 离线Tarjan算法,复杂度为:O(n+q)
  • 在线ST算法,把lca转换成rmq,复杂度为:O(NlogN)
  • 在线倍增算法,利用二进制加速找的过程,复杂度:O(NlogN)

下面只写Tarjan倍增算法,以洛谷的模板题:P3379 【模板】最近公共祖先(LCA)为例

题目有时候要求求出两个点之间的最短路,当使用离线Tarjan算法的时候,只需要用一个dis数组利用dfs来处理出路径的长度就可以。而使用在线倍增算法的时候,直接在倍增里面的dfs处理一下路径,答案显而易见,就是:dis[u]+dis[v]-2*dis[lca(u,v)]

离线Tarjan算法

讲解可以看这个文章:最近公共祖先(LCA)算法实现过程 【Tarjan离线+倍增在线+RMQ】,下面是我的模板:

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 1000000
#define mem(a,b) memset(a,b,sizeof(a))
const int N=500000+7;
int pre[N],first[N],first2[N],tot,tot2;
bool vis[N];//标记有没有询问
int n;
struct edge
{
    int v,next;
} e[2*N];
struct Query
{
    int v,w,next;
} query[2*N];

void add_edge(int u,int v)
{
    e[tot].v=v;
    e[tot].next=first[u];
    first[u]=tot++;
}

void add_query(int u,int v)
{
    query[tot2].v=v;
    query[tot2].w=-1;
    query[tot2].next=first2[u];
    first2[u]=tot2++;
}

int find(int x)
{
    return x==pre[x]?x:pre[x]=find(pre[x]);
}

int lca(int u,int fa)
{
    for(int i=first[u]; ~i; i=e[i].next)
    {
        int v=e[i].v;
        if(v==fa) continue;
        lca(v,u);
        pre[v]=u;
    }
    vis[u]=1;
    for(int i=first2[u]; ~i; i=query[i].next)
    {
        int v=query[i].v;
        if(vis[v])
            query[i].w=find(v);
    }
}

void init()
{
    mem(first,-1);
    mem(first2,-1);
    mem(vis,0);
    tot=0;
    tot2=0;
    for(int i=1; i<=n; i++)
        pre[i]=i;
}

int main()
{
    int m,s,u,v;
    scanf("%d%d%d",&n,&m,&s);
    init();
    for(int i=1; i<n; i++)
    {
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&u,&v);
        add_query(u,v);
        add_query(v,u);
    }
    lca(s,pre[s]);
    for(int i=0; i<tot2; i++)
        if(query[i].w!=-1)
            printf("%d\n",query[i].w);
    return 0;
}

在线倍增算法

讲解可以看这个文章:最近公共祖先(lca),下面是我的模板:

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stdlib.h>
#include <string>
#include <map>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define inf 1000000
#define mem(a,b) memset(a,b,sizeof(a))
const int N=500000+7;

int n,m,s;
int tot;
int first[N],d[N],p[N][21];

struct edge
{
    int v,next;
} e[2*N];

void add_edge(int u,int v)
{
    e[tot].v=v;
    e[tot].next=first[u];
    first[u]=tot++;
}

void dfs(int u,int fa)
{
    d[u]=d[fa]+1;
    p[u][0]=fa;
    for(int i=1; (1<<i)<=d[u]; i++)
        p[u][i]=p[p[u][i-1]][i-1];
    for(int i=first[u]; ~i; i=e[i].next)
    {
        int v=e[i].v;
        if(v!=fa)
            dfs(v,u);
    }
}

int lca(int a,int b)
{
    if(d[a]>d[b]) swap(a,b);//保证a在b点的上方
    for(int i=20; i>=0; i--)
        if(d[a]<=d[b]-(1<<i))
            b=p[b][i];  //把b移到和a同一个深度
    if(a==b) return a;
    for(int i=20; i>=0; i--)
    {
        if(p[a][i]==p[b][i])
            continue;
        else
            a=p[a][i],b=p[b][i];//一起向上跳跃
    }
    return p[a][0];
}


void init()
{
    tot=0;
    mem(first,-1);
    mem(d,0);
    mem(p,0);
}
int main()
{
    init();
    int a,b;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1; i<n; i++)
    {
        scanf("%d%d",&a,&b);
        add_edge(a,b);
        add_edge(b,a);
    }
    dfs(s,0);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",lca(a,b));
    }
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注