代码编织梦想

最近公共祖先LCA

LCA(Least Common Ancestors),即最近公共祖先,是指这样一个问题:在有根树中,找出某两个结点u和v最近的公共祖先(另一种说法,离树根最远的公共祖先)
在这里插入图片描述

最近公共祖先是相对于两个节点来说的,一般来说,最近公共祖先为节点 u和节点 v的最近的公共祖先。若 u 为 v 的祖先或者 v 为 u 的祖先,则LCA(u,v) 就是作为祖先的那个节点。示例图中 86 和 67的 LCA 是 75 ,61和 85的 LCA也是 75 。

LCA转RMQ

RMQ(Range Minimum/Maximum Query),即区间最值查询,是指这样一个问题:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在i,j之间的最小/大值。这两个问题是在实际应用中经常遇到的问题,本文介绍了当前解决这两种问题的比较高效的算法。

RMQ算法

对于该问题,最容易想到的解决方案是遍历,复杂度是O(n)。但当数据量非常大且查询很频繁时,该算法也许会存在问题。

介绍了一种比较高效的在线算法(ST算法)解决这个问题。所谓在线算法,是指用户每输入一个查询便马上处理一个查询。该算法一般用较长的时间做预处理,待信息充足以后便可以用较少的时间回答每个查询。ST(Sparse Table)算法是一个非常有名的在线处理RMQ问题的算法,它可以在O(nlogn)时间内进行预处理,然后在O(1)时间内回答每个查询。

首先是预处理,用动态规划(DP)解决。设A[i]是要求区间最值的数列,F[i, j]表示从第i个数起连续2^j个数中的最大值。例如数列3 2 4 5 6 8 1 2 9 7,F[1,0]表示第1个数起,长度为2^0=1的最大值,其实就是3这个数。 F[1,2]=5,F[1,3]=8,F[2,0]=2,F[2,1]=4……从这里可以看出F[i,0]其实就等于A[i]。这样,DP的状态、初值都已经有了,剩下的就是状态转移方程。我们把F[i,j]平均分成两段(因为f[i,j]一定是偶数个数字),从i到i+2(j-1)-1为一段,i+2(j-1)到i+2j-1为一段(长度都为2(j-1))。用上例说明,当i=1,j=3时就是3,2,4,5 和 6,8,1,2这两段。F[i,j]就是这两段的最大值中的最大值。于是我们得到了动态规划方程F[i, j]=max(F[i,j-1], F[i + 2^(j-1),j-1])。

然后是查询。取k=[log2(j-i+1)],则有:RMQ(A, i, j)=min{F[i,k],F[j-2^k+1,k]}。 举例说明,要求区间[2,8]的最大值,就要把它分成[2,5]和[5,8]两个区间,因为这两个区间的最大值我们可以直接由f[2,2]和f[5,2]得到。

算法伪代码:
//初始化
INIT_RMQ
//max[i][j]中存的是重j开始的2^i个数据中的最大值,最小值类似,num中存有数组的值
for i : 1 to n
  max[0][i] = num[i]
for i : 1 to log(n)/log(2)
  for j : 1 to (n+1-2^i)
     max[i][j] = MAX(max[i-1][j], max[i-1][j+2^(i-1)]
//查询
RMQ(i, j)
k = log(j-i+1) / log(2)
return MAX(max[k][i], max[k][j-2^k+1])

LCA算法

对于该问题,最容易想到的算法是分别从节点u和v回溯到根节点,获取u和v到根节点的路径P1,P2,其中P1和P2可以看成两条单链表,这就转换成常见的一道面试题:【判断两个单链表是否相交,如果相交,给出相交的第一个点。该算法总的复杂度是O(n)(其中n是树节点个数)
在线算法DFS+ST描述(思想是:将树看成一个无向图,u和v的公共祖先一定在u与v之间的最短路径上):

(1)DFS:从树T的根开始,进行深度优先遍历(将树T看成一个无向图),并记录下每次到达的顶点。第一个的结点是root(T),每经过一条边都记录它的端点。由于每条边恰好经过2次,因此一共记录了2n-1个结点,用E[1, … , 2n-1]来表示。

(2)计算R:用R[i]表示E数组中第一个值为i的元素下标,即如果R[u] < R[v]时,DFS访问的顺序是E[R[u], R[u]+1, …, R[v]]。虽然其中包含u的后代,但深度最小的还是u与v的公共祖先。

(3)RMQ:当R[u] ≥ R[v]时,LCA[T, u, v] = RMQ(L, R[v], R[u]);否则LCA[T, u, v] = RMQ(L, R[u], R[v]),计算RMQ。

由于RMQ中使用的ST算法是在线算法,所以这个算法也是在线算法。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
例题:
7 6 7个数6条边
3 7
3 4
4 5
4 6
5 1
6 2
求2和7的lca.
假如我们要询问 2 和7 的 LCA, 我们找到2和7 分别第一次出现的位置, 然后在这一个区间内找到深度最小的那个节点, 也就是节点 3, 显然它就是2 和7的 LCA.
在这里插入图片描述

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,cnt,tot=0,x,y,head[505],vis[505],dfn[505],de[505],ofs[505],dp[505][9],ru[505],root;
struct Egde{
    int to,next;
}edge[505];//表示边 
void add_edge(int bg,int ed)
{
    cnt++;
    edge[cnt].to=ed;
    edge[cnt].next=head[bg];
    head[bg]=cnt;
}
void dfs(int u,int dep)
{
    tot++;
    if(!vis[u]){
        vis[u]=1;dfn[u]=tot;
    }
    de[tot]=dep;
    ofs[tot]=u;
    for(int e=head[u];e>0;e=edge[e].next)
    {
        int v=edge[e].to;
        dfs(v,dep+1);
        ofs[++tot]=u;//通过这句话tot加,使dfn[]增加
    }
}
void init()//dp[]表示哪个tot
{
    for(int j=0;(1<<j)<=tot;j++)
    {
        for(int i=1;i+(1<<j)<=tot;i++)
        {
            if(j==0) dp[i][j]=i;
            else //dp用来存从i开始的2的j次方个区间内的最小值 
            {
                if(de[dp[i][j-1]]<de[dp[i+(1<<(j-1))][j-1]])
                    dp[i][j]=dp[i][j-1];
                else dp[i][j]=dp[i+(1<<(j-1))][j-1];//注意这里的左移外括号 
            }
        }
    }
}
int RMQ(int p1,int p2)//p1,p2是位置 
{
    int k=0;
    k=log2(p2-p1+1);
    if(de[dp[p1][k]]<de[dp[p2-(1<<k)+1][k]])
        return ofs[dp[p1][k]];
    else return ofs[dp[p2-(1<<k)+1][k]];
}
int lca(int v1,int v2)
{
    if(dfn[v1]<dfn[v2]) return RMQ(dfn[v1],dfn[v2]);//4,12 
    else RMQ(dfn[v2],dfn[v1]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        ru[y]++;
    }
    for(int i=1;i<=n;i++)if(ru[i]==0) root=i;
    dfs(root,1);
    init();
//  for(int i=1;i<=n;i++) 
//      for(int j=head[i];j>0;j=edge[j].next)
//          cout<<edge[j].to<<":"<<dfn[edge[j].to]<<" ";
//  cout<<endl;
    cout<<lca(2,7)<<endl;
}

倍增求LCA

在这里插入图片描述

以 17 和 18 为例,既然要求LCA,那么我们就让他们一个一个向上爬(我要一步一步往上爬 —— 《蜗牛》),直到相遇为止。第一次相遇即是他们的LCA。 模拟一下就是:
17->14->10->7->3
18->16->12->8->5->3
最终结果就是 3。

倍增算法

所谓倍增,就是按2的倍数来增大,也就是跳1,2,4,8,16,32 …… 不过在这我们不是按从小到大跳,而是从大向小跳,即按……32,16,8,4,2,1来跳,如果大的跳不过去,再把它调小。这是因为从小开始跳,可能会出现“悔棋”的现象。拿 5 为例,从小向大跳,5≠1+2+4,所以我们还要回溯一步,然后才能得出5=1+4;而从大向小跳,直接可以得出5=4+5=4+1。这也可以拿二进制为例,5(101),从高位向低位填很简单,如果填了这位之后比原数大了,那我就不填,这个过程是很好操作的。

还是以 17 和 18 为例(此例只演示倍增,并不是倍增LCA算法的真正路径):
17->3
18->5->3
可以看出向上跳的次数大大减小。这个算法的时间复杂度为O(nlogn),已经可以满足大部分的需求。

想要实现这个算法,首先我们要记录各个点的深度和他们2^i
级的的祖先,用数组\rm{depth}depth表示每个节点的深度,fa[i][j]fa[i][j]表示节点ii的2^j级祖先。 代码如下:

void dfs(int f,int fath) //f表示当前节点,fath表示它的父亲节点
{
depth[f]=depth[fath]+1;
fa[f][0]=fath;
for(int i=1;(1<<i)<=depth[f];i++)
  fa[f][i]=fa[fa[f][i-1]][i-1]; //这个转移可以说是算法的核心之一
                                //意思是f的2^i祖先等于f的2^(i-1)祖先的2^(i-1)祖先
                                //2^i=2^(i-1)+2^(i-1)
for(int i=head[f];i;i=e[i].nex)
  if(e[i].t!=fath)
    dfs(e[i].t,f);
}

预处理完毕后,我们就可以去找它的LCA了,为了让它跑得快一些,我们可以加一个常数优化。

for(int i=1;i<=n;i++) //预先算出log_2(i)+1的值,用的时候直接调用就可以了
  lg[i]=lg[i-1]+(1<<lg[i-1]==i);  //看不懂的可以手推一下

接下来就是倍增LCA了,我们先把两个点提到同一高度,再统一开始跳。

但我们在跳的时候不能直接跳到它们的LCA,因为这可能会误判,比如4和8,在跳的时候,我们可能会认为1是它们的LCA,但1只是它们的祖先,它们的LCA其实是3。所以我们要跳到它们LCA的下面一层,比如4和8,我们就跳到4和5,然后输出它们的父节点,这样就不会误判了。

int lca(int x,int y)
{
if(depth[x]<depth[y]) //用数学语言来说就是:不妨设x的深度 >= y的深度
  swap(x,y);
while(depth[x]>depth[y])
  x=fa[x][lg[depth[x]-depth[y]]-1]; //先跳到同一深度
if(x==y)  //如果x是y的祖先,那他们的LCA肯定就是x了
  return x;
for(int k=lg[depth[x]]-1;k>=0;k--) //不断向上跳(lg就是之前说的常数优化)
  if(fa[x][k]!=fa[y][k])  //因为我们要跳到它们LCA的下面一层,所以它们肯定不相等,如果不相等就跳过去。
    x=fa[x][k], y=fa[y][k];
return fa[x][0];  //返回父节点
}

完整的求17和18的LCA的路径:
17->10->7->3
18->16->8->5->3
解释:首先,18要跳到和17深度相同,然后18和17一起向上跳,一直跳到LCA的下一层(17是7,18是5),此时LCA就是它们的父亲。

Tarjan求LCA

Tarjan

int f[maxn],fs[maxn];//并查集父节点 父节点个数
bool vit[maxn];
int anc[maxn];//祖先
vector<int> son[maxn];//保存树
vector<int> qes[maxn];//保存查询
typedef vector<int>::iterator IT;
 
int Find(int x)
{
    if(f[x]==x) return x;
    else return f[x]=Find(f[x]);
}
void Union(int x,int y)
{
    x=Find(x);y=Find(y);
    if(x==y) return;
    if(fs[x]<=fs[y]) f[x]=y,fs[y]+=fs[x];
    else f[y]=x,fs[x]+=fs[y];
}
 
void lca(int u)
{
    anc[u]=u;
    for(IT v=son[u].begin();v!=son[u].end();++v)
    {
        lca(*v);
        Union(u,*v);
        anc[Find(u)]=u;
    }
    vit[u]=true;
    for(IT v=qes[u].begin();v!=qes[u].end();++v)
    {
        if(vit[*v])
            printf("LCA(%d,%d):%d\n",u,*v,anc[Find(*v)]);
    }
}

练习

1、求最近公共祖先
建议使用倍增和Tarjan两种方法写

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_32431299/article/details/125670874

【C++】最近公共祖先 LCA-爱代码爱编程

最近公共祖先 百科名片简单引入LCA的算法暴力枚举法Tarjan离线算法倍增算法例题:题目描述输入描述输出描述样例输入样例输出代码 百科名片 最近公共祖先Lowest Common AncestorsLCA简单引入 对于有根树T的两个结点u、v,最近公共祖先LCA(T,u,v)表示一个结点x,满足x是u、v的祖先且x的深度尽可能大。 红色的

图论 -> 最近公共祖先(LCA)习题-爱代码爱编程

1. 祖孙询问 /* * Author: Chen_zhuozhuo * Created Time: 2020/3/28 16:22:33 * File Name: a.cpp */ #include <iostream> #include <cstdio> #include <cstdlib> #incl

图论---最近公共祖先(LCA)-爱代码爱编程

最近公共祖先 (Least Common Ancestors,LCA)问题:给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。 Tarjan算法解决 LCA 虽然也叫Tarjan算法,但是并不是求强连通分量的Tarjan算法。Tarjan很厉害,他发明了很多算法。。。 Tarjan算法解决LCA问题,基于深度优先搜索。我们能想到,对于一棵树的根

最近公共祖先 python_『图论』LCA最近公共祖先(示例代码)-爱代码爱编程

概述篇 LCA(Least Common Ancestors),即最近公共祖先,是指这样的一个问题:在一棵有根树中,找出某两个节点 u 和 v 最近的公共祖先。 LCA可分为在线算法与离线算法 在线算法:指程序可以以序列化的方式一个一个处理输入,也就是说在一开始并不需要知道所有的输入。 离线算法:指一开始就需要知道问题的所有输入数据,而在解

最近公共祖先LCA倍增算法-爱代码爱编程

LCA定义 LCA(Least Common Ancestors):最近公共祖先即两个结点最近的公共祖先 由上图可以看到 5号结点和7号结点的LCA为3号结点,9号结点和7号结点的LCA为7号结点。 一般算法 首先可以将两个结点统一到相同深度,然后一起向上一步一步走,直到他们踩到相同点,则该点为他们的LCA 。 (

图论之最近公共祖先------LCA倍增算法-爱代码爱编程

1.祖孙询问(模板题) #include <iostream> #include <cstring> #include <algorithm> #include<cstdio> using namespace std; const int N = 40010,M=2*N; int n,m; int h[N]

236-二叉树的最近公共祖先-爱代码爱编程

题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 示例 1: 输入:root = [3,5,1,6,2,0,8,null,null,7,4], p

最近公共祖先 LCA-爱代码爱编程

概念 子节点(儿子):一个节点含有的子树的根节点称为该节点的子节点; 父节点(父亲):若一个节点含有子节点,则这个节点称为其子节点的父节点; 根节点:没有父节点的节点; 兄弟节点:具有相同父节点的节点互称为兄弟节点; 祖先:父亲以及父亲的祖先; 后代:儿子以及儿子的后代; 子树:子节点及其后代构成的树 节点的度:一个节点相连的点的个数称为该

最近公共祖先(LCA)-爱代码爱编程

最近公共祖先 向上标记法树上倍增Tarjan发明的算法转化为求区间最小值问题 最近公共祖先问题是树中的常考问题,比如我们有一棵树(可以是多叉的),两个点的最近公共祖先就是字面的意思,比如说6、5节点的最近公共祖先就是2,而4和7的最近公共祖先我们规定为4. 最近公共祖先问题就是给我们两个点让我们求他们的最近公共祖先的问题。 下面我就介绍一下我

【算法题归纳合集】图论-最近公共祖先-爱代码爱编程

一、AcWing 1172. 祖孙询问(倍增法) 【题目描述】 给定一棵包含 n n n个节点的有根无向树,节点编号互不相同,但不一定是

【图论】—— 最近公共祖先(lca)_玄澈_的博客-爱代码爱编程

给定一颗树,若节点 z 既是 节点 x 的祖先, 也是节点 y 的祖先,那么称 z 为 x、y 的公共祖先。 在 x、y 的所有公共祖先中,深度最大的一个称为 x、y 的最近公共祖先, 也称 LCA(x, y) LCA(x, y) 是 x 到根的路径与 y 到根的路径的交汇点。它也是 x 与 y 之间的路径上深度最小的节点。 树上倍增法

图论(最近公共祖先lca)_dαīsч的博客-爱代码爱编程

一、基础 1、定义:在一棵有根树上,对于一个结点z,既是x的祖先,也是y的祖先,那么z是x,y的公共祖先,如果z在x,y的所有公共祖先中深度最大的,我们称之为最近公共祖先,记z = LCA(x,y) 2、暴力寻找(最坏时间复杂度O(n)): (1)、从x向上走到根节点,并且标记经过的结点,然后令y向上走到根节点,当第一次遇到已标记的点时,就找到了LC

b -爱代码爱编程

You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move