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

最近公共祖先详解_共同祖先最近公共祖先带查询的节点为x和y节点,书的深度为d暴力求解:设置访问数组vis[N],以此遍历x的父节点并做标记,然后再遍历y的父节点,第一个被做标记的就是公共祖先,时间复杂度为O(d)倍增法:f[i][j]代表当前节点向上走2j2^j2j所能走到的节点,其中0≤j≤⌈log(d)⌉0\leq j \leq \lceil log(d) \rceil0≤j≤⌈log(d)⌉,时间复杂度为O(logn),另外还需要设置dist[N]代表节点i到根的距离+1,哨兵:如果从i开始跳2j2^j2j步会跳过根节

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

最近公共祖先

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

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

倍增法

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

预处理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;
    }
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168771.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • java冒泡排序经典代码_java冒泡排序[通俗易懂]

    java冒泡排序经典代码_java冒泡排序[通俗易懂]经典算法——冒泡排序(BubbleSort)一、示例代码(伸手党看这里)1.示例一importjava.util.Arrays;publicclassBubbleSort{publicstaticvoidbubbleSort(int[]arr){inttemp;/*临时变量,交换数据时使用*/intlength=arr.length;for(intp=length-1…

  • 进销存excel_用Excel制作简单的进销存系统「建议收藏」

    进销存excel_用Excel制作简单的进销存系统「建议收藏」最近刚好帮一个朋友做一个进销存系统,因为使用者对电脑操作以及Excel应用能力较弱,我做的进销存系统没有用特别复杂的功能,非常有解决意义,我将手把手将你制作一个简单的进销存系统。需求描述朋友找人合伙开了一个女装店,想要用Excel记录每天的销售数据、定期的进货数据,以及定期盘点库存情况。朋友的合伙人对电脑操作、Excel数据管理能力较弱,前期购买过专用的进销存软件,但是经常会把数据搞乱,因此放弃了…

  • 我在做的测试框架

    我在做的测试框架

  • 常量表达式(const expression)

    常量表达式(const expression)常量表达式是指值不会改变并且在编译过程中就能得到计算结果的表达式问:intstaff_size=27; constintsz=get_size();是不是常量表达式?答:intstaff_size=27; //staff_size不是常量表达式constintsz=get_size(); //sz不是常量表达式staff_size的数据类型是int而不是constint,是可以改变的,而且get_size()的值直到运行时才能获取到

  • PHP中对PSR-1、PSR-2规范理解

    PHP中对PSR-1、PSR-2规范理解

  • 初识java——hello world(代码讲解很详细)[通俗易懂]

    初识java——hello world(代码讲解很详细)[通俗易懂]在每学一门语言之前我们首先要学会helloworld的的写法,下面我用java写了一个hello的输出以及每行代码的讲解;publicclasshelloworld{publicstaticvoidmain(String[]args){System.out.println(“helloworld!”);System.out.printf(“helloworld!!\n”);System.out.print(“hellow

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号