【图论】LCA(倍增)

这篇具有很好参考价值的文章主要介绍了【图论】LCA(倍增)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一.LCA介绍

【图论】LCA(倍增),图论,图论

LCA通常指的是“最近共同祖先”(Lowest Common Ancestor)。LCA是一种用于解决树或图结构中两个节点的最低共同祖先的问题的算法。

在树结构中,LCA是指两个节点的最近层级的共同祖先节点。例如,考虑一棵树,其中节点A是节点B和节点C的祖先,而节点D是节点B和节点C的共同祖先,但节点D不是最低层级的共同祖先。在这种情况下,LCA就是节点D。

LCA算法在计算机科学中有广泛的应用,例如在计算树的最近公共祖先、解决图的连通性问题、计算有向无环图(DAG)的最近公共祖先等方面。常见的LCA算法包括基于深度优先搜索(DFS)的算法、基于倍增法的算法和Tarjan算法等。

LCA算法的实现方式取决于所使用的数据结构和具体问题的要求。它可以通过预处理树结构,计算和存储每个节点的深度或其他相关信息,以加快查询的速度。LCA算法的时间复杂度通常为O(logN)或O(1),其中N是树或图中的节点数量。

总之,LCA算法是解决树或图结构中两个节点最低共同祖先的问题的一种常见算法。


 二.倍增法求LCA

【图论】LCA(倍增),图论,图论

 倍增法(Binary Lifting)是一种常用的求解最低共同祖先(LCA)问题的算法。它通过预处理和存储每个节点的跳跃祖先,以实现快速查询LCA的目的。下面是倍增法求解LCA的详细步骤:

  1. 预处理:对于每个节点v,计算并存储它的第2^i个祖先,其中i从0开始逐渐增加。这可以通过深度优先搜索(DFS)遍历树来完成。对于根节点,其第2^i个祖先就是根节点本身。对于其他节点v,其第2^i个祖先可以通过它的第2^(i-1)个祖先的第2^(i-1)个祖先来计算。

  2. 查询LCA:给定两个节点u和v,首先比较它们的深度,假设u的深度大于v的深度。然后,通过不断向上跳跃u的祖先,使得u和v的深度相等。具体步骤如下:

    • 如果u和v的深度不相等,将u向上跳跃到与v深度相等的位置。这可以通过从最高位开始逐渐减小的方式进行,即从最大的i开始,如果u的第2^i个祖先的深度大于等于v的深度,则将u跳跃到第2^i个祖先。
    • 然后,同时向上跳跃u和v,直到它们的第一个公共祖先出现。这可以通过从最高位开始逐渐减小的方式进行,即从最大的i开始,如果u的第2^i个祖先和v的第2^i个祖先不相等,则将u和v同时跳跃到它们的第2^i个祖先。
    • 最后,u和v的第一个公共祖先就是LCA。

倍增法求解LCA的时间复杂度为O(logN),其中N是树中的节点数量。这是因为在查询LCA时,每次跳跃都会将节点的深度减半,直到找到LCA为止。

总结起来,倍增法是一种通过预处理存储节点的跳跃祖先来求解LCA问题的算法。它具有较低的时间复杂度,并且适用于静态树结构,即树结构不会发生变化的情况下。

 


三.题目

P3379 【模板】最近公共祖先(LCA) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)


四.代码

#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
int n,m,s; //点,次数,根节点 
//链式前向星
int cnt=0,head[maxn];
struct Edge{
	int u,v,next;
}edge[maxn<<1]; 
void add(int u,int v){
	edge[++cnt]=(Edge){u,v,head[u]};head[u]=cnt;
}
//建树
int depth[maxn],p[maxn][25];
void dfs(int u,int fa){
	p[u][0]=fa;
	depth[u]=depth[fa]+1;
	for(int i=head[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(v==fa) continue; //防止套娃,无线循环
		dfs(v,u); 
	}
} 
int lca(int x,int y){
	if(depth[x]<depth[y]) swap(x,y);
	for(int j=24;j>=0;j--){
		if(depth[x]-(1<<j)>=depth[y]){
			x=p[x][j]; //往上走 
		}
	}
	//特判&&巧合
	if(x==y) return x;
	//现在x和y深度差不多,同时上升
	for(int j=24;j>=0;j--){
		if(p[x][j]!=p[y][j]){
			x=p[x][j]; y=p[y][j];
		}
	} 
	return p[x][0];
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;add(u,v);add(v,u);
	}
	dfs(s,0); //建树 
	//预处理 
	for(int j=1;(1<<j)<=n;j++){ //长度  2^j<=n 
		for(int i=1;i<=n;i++){
			p[i][j]=p[p[i][j-1]][j-1];
		}
	} 
	//输出答案&&LCA
	while(m--){
		int x,y;cin>>x>>y;
		cout<<lca(x,y)<<endl;
	} 
	return 0;
}

五.卡住笔者的一个小问题

【图论】LCA(倍增),图论,图论


 

六.answer:

注意:【图论】LCA(倍增),图论,图论

找到p[x][j]!=p[y][j]的时候,并没有直接break;

而是赋值后继续,也就是意味着(结合我的疑问)j再=0,再往上跳1步才结束

这时就成功到达pick点,最后return p[x][0]即为LCA;

其实就妙在遍历中找到!=时,赋值后继续遍历,这就解决了LCA不在倍增数的情况! 文章来源地址https://www.toymoban.com/news/detail-613921.html

到了这里,关于【图论】LCA(倍增)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第三章 图论 No.8最近公共祖先lca, tarjan与次小生成树

    O ( m l o g n ) O(mlogn) O ( m l o g n ) ,n为节点数量,m为询问次数,lca是一种在线处理询问的算法 自己也是自己的祖先 倍增: f a ( i , j ) fa(i, j) f a ( i , j ) 表示从i开始,向上走 2 j 2^j 2 j 步走到的点 j = 0,走到父节点 j 0,分两步走,先走到 2 j − 1 2^{j-1} 2 j − 1 步再走 2 j − 1 2^{

    2024年02月13日
    浏览(44)
  • 第三章 图论 No.3 flody之多源汇最短路,传递闭包,最小环与倍增

    flody的四个应用: 多源汇最短路 传递闭包 找最小环 恰好经过k条边的最短路 倍增 多源汇最短路:1125. 牛的旅行 1125. 牛的旅行 - AcWing题库 直径概念:同一连通块中,两个距离最远的点之间的距离 如何求直径?由于图中存在着两个连通块,所以直接对全图做一个flody,就能更

    2024年02月14日
    浏览(45)
  • 【算法】倍增-ST表

     倍增是一种常用的算法技巧,通常用于优化时间复杂度。它的核心思想是将原问题分解成若干个规模较小的子问题,通过对子问题的求解来得到原问题的解。具体来说,倍增算法通常采用二分思想,将问题规模不断缩小,直到问题规模足够小,可以直接求解。 在计算机科学

    2024年02月11日
    浏览(26)
  • 最近公共祖先(LCA)

    「观前提醒」 「文章仅供学习和参考,如有问题请在评论区提出」 目录 前言 定义 性质 求 LCA 倍增算法 Trajan 算法 树链剖分 基本概念 基本性质 具体实现 参考资料 简单的模板整理,只是概括了一下具体的实现方法(说到底是给自己写的),如果看不明白可以去看原视频(讲

    2024年02月14日
    浏览(38)
  • 求解 LCA の方法

    最近公共祖先简称 LCA(Lowest Common Ancestor)。两个节点的最近公共祖先,就是这两个点的公共祖先里面,离根最远的那个。 -----oi wiki 举个例子 在这张图中, (5) 和 (9) 的最近公共祖先就是 (3) , (9) 和 (7) 的最近公共祖先就是 (2) 由于在树上两点间的简单路径是唯一的

    2024年02月02日
    浏览(47)
  • 最长公共子序列LCA

    题目链接:3692. 最长连续公共子序列 - AcWing题库

    2024年02月13日
    浏览(39)
  • LCA——ST表+欧拉序

    了解到一个quan新的东西: 用ST表(欧拉序)实现LCA(树上最近公共祖先) 前序遍历得到的序列,叫dfs序 但数字可以重复出现,一进一出,叫欧拉序 会发现根结点总在中间 而根结点是该段序列深度最小的点 因此两个点的LCA, 就是在 该序列上两个点第一次出现的区间内深度最小

    2024年02月02日
    浏览(32)
  • 【算法】LCA的三种算法

    LCA(Least Common Ancestors),即最近公共祖先,是指在有根树中,找出某两个结点x和y最近的公共祖先。 用三种算法可以求解LCA问题,分别为朴素算法、倍增算法和Tarjan算法。 倍增算法和Tarjan算法都在建立在朴素算法的思想下,因此,了解朴素算法的思想有助于更好的理解进阶算法

    2024年03月19日
    浏览(28)
  • 【树上差分+LCA】篮球杯 砍树

    省赛的题现在来补 感觉什么都不会,已经要没了 题意: 思路: 考虑一条边,两端有两棵子树 有这样的性质: 这条边两端的结点的经过次数==M  因此每加一个点对,都对其路径+1 s[u]==M时,与该点连着的边就是合法边了,统计合法边的最大id就行 Code:

    2024年02月06日
    浏览(52)
  • 【数据结构:线性表】倍增表(ST表)

    一 . 基本概念 ST表:又名稀疏表,用来处理 区间最值查询 的 离线 算法, 用到了 倍增 的思想 某个区间查询问题是否适用ST表,关键在于其进行的操作是否允许区间重叠。 例如max(a,b,c) = max{max(a,b),max(b,c)}就可以用ST表维护,而 区间和 问题则不能维护。 在时间复杂度上:预处

    2024年02月11日
    浏览(27)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包