首页 > > 程序设计 > C/C++ >

浅谈LCA

2019-12-25 16:03:47来源：博客园阅读 ()

浅谈LCA

最近公共祖先LCA

如图

LCA(4,5)=8

LCA(10,16)=10

LCA(7,3)=4

求LCA主要算法有：RMQ,tarjan,倍增

RMQ

这种方法就是打表

O(n logn)预处理，O(1)回答

RMQ就是区间最值查询。

首先通过dfs求出每个点的深度

显然，两个节点的LCA不仅是两个节点的最近公共祖先，而且包括这两个节点的最小子树的根，即包括这两个节点的最小子树中的深度最小的节点。

现在，我们改一下dfs，变成欧拉序。

欧拉序，就是每次从x的父亲进入节点x或者从子节点回溯到x都要把x这个编号扔到一个数组的最后。

如图

欧拉序为：8 5 9 5 8 4 6 15 6 7 6 4 10 11 10 16 3 16 12 16 10 2 10 4 8 1 14 1 13 1 8

再注意到，一对点的 LCA 不仅是包括这两个节点的最小子树中的深度最小的节点，还是连接这对点的简单路径上深度最小的点。

而且从离开x到进入y的这段欧拉序必然包括所有这对点之间的简单路径上的所有点，所以我们考虑求得这段欧拉序中所包含的节点中的深度最小的点,即他们的LCA。

从x到y的这段欧拉序会包含这棵子树中的其他节点，但是不会影响这个最浅点的求得。

显然，x到y这段欧拉序是个连续区间。

现在我们考虑通过预处理来O(1)获得这个最浅点。

这里有一个叫做ST表的东西。

代码

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int to,next;
}ed[100005];
int n,q,u,v,cnt,head[50005],ind,dfn[50005],dep[50005],lg[50005],f[50005][21];
void add(int u,int v){
    cnt++;
    ed[cnt].to=v;
    ed[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int fa){
    dfn[u]=++ind;
    dep[u]=dep[fa]+1;
    f[ind][0]=u; 
    for(int i=head[u];i;i=ed[i].next){
        int v=ed[i].to;
        if(v!=fa)dfs(v,u),f[++ind][0]=u;
    }
}
void st(){
    for(int j=1;j<=20;j++){
        for(int i=1;i+(1<<j)<=ind+1;i++){
            int k=i+(1<<(j-1));
            if(dep[f[i][j-1]]<dep[f[k][j-1]])f[i][j]=f[i][j-1];
            else f[i][j]=f[k][j-1];
        }
    }
}
int rmq(int l,int r){
    if(l>r)swap(l,r);
    int k=lg[r-l+1];
    if(dep[f[l][k]]<dep[f[r-(1<<k)+1][k]])return f[l][k];
    else return f[r-(1<<k)+1][k];
}
int main(){
    scanf("%d%d",&n,&q);
    lg[0]=-1;
    for(int i=1;i<=n;i++)lg[i]=lg[i/2]+1;
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs(1,0);
    st();
    for(int i=1;i<=q;i++){
        scanf("%d%d",&u,&v);
        printf("%d\n",rmq(dfn[u],dfn[v]));
    }
}

Tarjan

一种离线算法，要用到并查集。

时间复杂度为O(n+q)。

Tarjan算法基于dfs，在dfs的过程中，对于每个节点位置的询问做出相应的回答。

dfs的过程中，当一棵子树被搜索完成之后，就把他和他的父亲合并成同一集合；在搜索当前子树节点的询问时，如果该询问的另一个节点已经被访问过，那么该编号的询问是被标记了的，于是直接输出当前状态下，另一个节点所在的并查集的祖先；如果另一个节点还没有被访问过，那么就做下标记，继续dfs。

如图

比如：8−1−14−13,此时已经完成了对子树1的子树14的dfs与合并，如果存在询问(13,14)，则其LCA即find(14)，即1；如果还存在由节点13与已经完成搜索的子树中的节点的询问，那么处理完。然后合并子树13的集合与其父亲1当前的集合，回溯到子树1，并深搜完所有1的其他未被搜索过的儿子，并完成子树1中所有节点的合并，再往上回溯，对节点1进行类似的操作即可。

代码

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int to,next;
}ed[50005];
struct qedge{
    int to,next,lca;
}qed[50005];
int n,q,u,v,cnt,qcnt,head[50005],qhead[50005],fa[50005];
void add(int u,int v){
    cnt++;
    ed[cnt].to=v;
    ed[cnt].next=head[u];
    head[u]=cnt;
}
void qadd(int u,int v){
    qcnt++;
    qed[qcnt].to=v;
    qed[qcnt].next=qhead[u];
    qhead[u]=qcnt;
}
int find(int x){
    return fa[x]==x?x:find(fa[x]);
}
void dfs(int u,int pa){
    fa[u]=u;
    for(int i=head[u];i;i=ed[i].next){
        int v=ed[i].to;
        if(v!=pa){
            dfs(v,u);
            fa[v]=u;
        }
    }
    for(int i=qhead[u];i;i=qed[i].next){
        int v=qed[i].to;
        if(v!=pa&&!qed[i].lca){
            qed[i].lca=find(v);
            if(i%2)qed[i+1].lca=qed[i].lca;
            else qed[i-1].lca=qed[i].lca;
        }
    }
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    for(int i=1;i<=q;i++){
        scanf("%d%d",&u,&v);
        qadd(u,v),qadd(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=q;i++)printf("%d\n",qed[2*i].lca);
}

倍增

时间复杂度O((n+q)logn)

对于这个算法，我们从最暴力的算法开始：

①如果x和y深度不同，先把深度调浅，使他变得和深度小的那个一样

②现在已经保证了x和y的深度一样，所以我们只要把两个一起一步一步往上移动，直到他们到达同一个节点，也就是他们的最近公共祖先了。

代码

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int to,next;
}ed[100005];
int n,q,u,v,cnt,head[50005],dep[10005],fa[10005];
void add(int u,int v){
    cnt++;
    ed[cnt].to=v;
    ed[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int pa){
    dep[u]=dep[pa]+1,fa[u]=pa;
    for(int i=head[u];i;i=ed[i].next){
        int v=ed[i].to;
        if(v!=pa)dfs(v,u);
    }
}
int lca(int u,int v){
    if(u==v)return u;
    if(dep[u]==dep[v])return lca(fa[u],fa[v]);
    if(dep[u]>dep[v])return lca(fa[u],v);
    if(dep[u]<dep[v])return lca(u,fa[v]);
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=q;i++){
        scanf("%d%d",&u,&v);
        printf("%d\n",lca(u,v));
    }
}

但这样一步一步往上移动太慢，我们可以做一个预处理：

设f_i,j表示从结点i开始向上走2^j步到达的点，所以f_i,0=fa(i),f_i,1=f_f[0][0],0,$f_i,j=f_{f[i][j-1],i-j}$

如图

f_5,0=5

f_7,1=4

f_3,2=f_{f[3][2-1],2-1}=f_10,1=8

于是我们可以得出以下做法：

1.把x和y移到同一深度（设dep_x为节点x的深度），假设dep_x<dep_y，从大到小枚举k，如果dep_f[y][k]≠dep_x，那么y就往上跳。

2.如果x=y，那么显然LCA就是f_x,0。否则执行第3步。

3.在xx≠yy的情况下找到深度最小的xx和yy。

代码

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int to,next;
}ed[100005];
int n,q,u,v,cnt,head[50005],dep[50005],f[50005][20];
void add(int u,int v){
    cnt++;
    ed[cnt].to=v;
    ed[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int fa){
    f[u][0]=fa;
    dep[u]=dep[fa]+1;
    for(int i=1;i<20;i++)f[u][i]=f[f[u][i-1]][i-1];
    for(int i=head[u];i;i=ed[i].next){
        int v=ed[i].to;
        if(v!=fa)dfs(v,u);
    }
}
int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int i=19;i>=0;i--)if(dep[u]-(1<<i)>=dep[v])u=f[u][i];
    if(u==v)return u;
    for(int i=19;i>=0;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
    return f[u][0];
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=q;i++){
        scanf("%d%d",&u,&v);
        printf("%d\n",lca(u,v));
    }
}