最近公共祖先详解_共同祖先

全栈程序员站长

发布于 2022-09-22 09:45:03

5890

文章被收录于专栏：全栈程序员必看全栈程序员必看

最近公共祖先

带查询的节点为x和y节点，书的深度为d

暴力求解：设置访问数组vis[N],以此遍历x的父节点并做标记，然后再遍历y的父节点，第一个被做标记的就是公共祖先，时间复杂度为O(d)
倍增法：f[i][j]代表当前节点向上走 2 j 2^j 2j所能走到的节点，其中 0 ≤ j ≤ ⌈ l o g ( d ) ⌉ 0\leq j \leq \lceil log(d) \rceil 0≤j≤⌈log(d)⌉，时间复杂度为O(logn)，另外还需要设置dist[N]代表节点i到根的距离+1，哨兵：如果从i开始跳 2 j 2^j 2j步会跳过根节点，那么f[i][j] = 0,dist[root]=0
Tarjan离线算法：将每一个搜索过的点归类到他的代表节点中去，代表节点就是搜索过的节点与当前节点的公共祖先。时间复杂度O(n)

倍增法

先将两个点跳到同一层
再让两个点往上跳，一直跳到他们的公共祖先的下一个几点。我们跳的时候是基于二进制拼凑的思想，从最高位到最低位判断。

预处理f[i][j]时间复杂度：nlog(n) 查询O(logn)

倍增法(bfs)代码

int fa[N][16],depth[N];
int q[N],hh = 0,tt = 0;
int head[N],cnt;
struct Edge{ 
   
    int v,next;
}edge[M];
void add(int u,int v){ 
   
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
void bfs(int root){ 
        //预处理
    memset(depth,INF,sizeof depth);
    q[0] = root;
    depth[0] = 0;
    depth[root] = 1,fa[root][0] = 0;
    while(hh <= tt){ 
   
        int t = q[hh ++];
        for(int i = head[t];~i;i = edge[i].next){ 
   
            int ver = edge[i].v;
            if(depth[ver] < depth[t] + 1)continue;
            depth[ver] = depth[t] + 1;
            q[++ tt] = ver;
            fa[ver][0] = t;
            for(int k = 1;k < 16;k ++){ 
   
                fa[ver][k] = fa[fa[ver][k - 1]][k - 1];
            }
        }
    }
}
int lca(int a,int b){ 
   
    if(depth[a] < depth[b])swap(a,b);
    for(int k = 15;k >= 0;k --)
        if(depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    if(a == b)return a;
    for(int k = 15;k >= 0;k --)
        if(fa[a][k] != fa[b][k]){ 
   
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}

Tarjan

struct Edge{ 
   
    int v,next;
}edge[M];
void add(int u,int v){ 
   
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
void init(){ 
   
    for(int i = 0;i < N;i ++)fa[i] = i;
}
int Find(int x){ 
   
    return fa[x] = (fa[x] == x ? x : Find(fa[x]));
}
void Tarjan(int u,int f){ 
   
    vis[u] = true;
    for(auto &q : query[u]){ 
   
        int y = q.x,id = q.y;
        if(vis[y])res[id] = Find(y);    //如果之前遍历过另一个节点
    }
    for(int i = head[u];~i;i = edge[i].next){ 
   
        int ver = edge[i].v;
        if(ver == f)continue;
        Tarjan(ver,u);
        fa[ver] = u;
    }
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168771.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

https