LCA算法——倍增

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LCA算法——倍增，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1728字，纯文字阅读大概需要3分钟。

内容图文

概况

LCA（Lowest Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。

实现过程 预处理：通过dfs遍历，记录每个节点到根节点的距离dist[u]，深度d[u] init()求出树上每个节点u的2^i祖先p[u][i] 求最近公共祖先，根据两个节点的的深度，如不同，向上调整深度大的节点，使得两个节点在同一层上，如果正好是祖先结束，否则，将两个节点同时上移，查询最近公共祖先。 代码：

#include<bits/stdc++.h>
#include<queue>
using namespace std;
const int N=5e5+5;
int n,m,s;
int root;
int idx=1;
int ver[2*N],nex[2*N],head[2*N],dis[2*N],f[2*N][25];
queue<int>q;
int t;

void add(int x,int y) {//邻接表建图
    ver[++idx]=y;
    nex[idx]=head[x];
    head[x]=idx;
    return ;
}

void bfs() {//bfs会比dfs更加保险
    q.push(root);
    dis[root]=1;//根节点的深度为1
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        for(int i=head[x]; i; i=nex[i]) {//向下一层搜索
            int y=ver[i];
            if(dis[y]) continue;//防止死循环
            dis[y]=dis[x]+1;//深度更新
            f[y][0]=x;//2^0=1,即为y的父结点
            for(int j=1; j<=t; j++) {
                f[y][j]=f[f[y][j-1]][j-1];//更新2^i个祖先
            }
            q.push(y);
        }
    }
    return ;
}

int lca(int x,int y) {
    if(dis[x]<dis[y]){//严格规范dis[x]>dis[y]
        swap(x,y);    
    } 
    for(int i=t; i>=0; i--) {
        if(dis[f[x][i]]>=dis[y]) x=f[x][i];//使x和y的深度相同
    }
    if(x==y) return x;//已经相同，则直接返回x
    for(int i=t; i>=0; i--) {
        if(f[x][i]!=f[y][i]) {//如果第2^i个祖先不相同，说明还没有到最小公共祖先
            x=f[x][i];
            y=f[y][i];//更新x,y
        }
    }
    return f[x][0];//返回x的父节点——即最小公共祖先
}

int main() {
    cin>>n;
    t=(log(n)/log(2))+1;
    for(int i=1; i<=n; i++) {
        int a,b;
        cin>>a>>b;
        if(b==-1) root=a;
            add(a,b);
            add(b,a);
    }
    bfs();
    cin>>m;
    for(int i=1; i<=m; i++) {
        int x,y;
        cin>>x>>y;
        if(lca(x,y)==x) cout<<1<<endl;
        if(lca(x,y)==y) cout<<2<<endl;
        if(lca(x,y)!=x&&lca(x,y)!=y) cout<<0<<endl;
    }
//    for(int i=1;i<=5;i++)cout<<i<<":"<<dis[i]<<endl;
    return 0;
}

 

内容总结

以上是互联网集市为您收集整理的LCA算法——倍增全部内容，希望文章能够帮你解决LCA算法——倍增所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---