DataStructure

最近公共祖先(LCA-tarjan/RMQ/倍增)

2019-07-27  本文已影响0人  雨落八千里
  • 在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节 换句话说，就是两个点在这棵树上距离最近的公共祖先节点。
    有人可能会问：那他本身或者其父亲节点是否可以作为祖先节点呢？答案是肯定的，很简单，按照人的亲戚观念来说，你的父亲也是你的祖先，而LCA还可以将自己视为祖先节点。
    求LCA算法常用的三种tarjan/倍增/ST

tarjan求LCA原理：

声明下面内容参考：大佬传送门https://www.cnblogs.com/JVxie/p/4854719.html
　举个例子吧，如下图所示４和５的最近公共祖先是２，５和３的最近公共祖先是１，２和１的最近公共祖先是１。　

这就是最近公共祖先的基本概念了，那么我们该如何去求这个最近公共祖先呢？

什么是Tarjan(离线)算法呢？顾名思义，就是在一次遍历中把所有询问一次性解决，所以其时间复杂度是O(n+q)。

Tarjan算法的优点在于相对稳定，时间复杂度也比较居中，也很容易理解。

下面详细介绍一下Tarjan算法的基本思路：

1. 任选一个点为根节点，从根节点开始。

2.遍历该点u所有子节点v，并标记这些子节点v已被访问过。

3.若是v还有子节点，返回2，否则下一步。

4.合并v到u上。

5.寻找与当前点u有询问关系的点v。

6.若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合
并到的父亲节点a。

遍历的话需要用到dfs来遍历(我相信来看的人都懂吧...)，至于合并，最优化的方式就是利用并查集来合并两个节点。

void dfs(int u)
{
    vis[u]=1;
    for(int i=0;i<ve[u].size();i++)//遍历子节点
    {
        int v=ve[u][i];
        dfs(ve[u][i]);//还有子节点
        ouin(u,ve[u][i]);//合并父子节点
    }
    for(int j=0;j<pp[u].size();j++)//寻找当前点u有询问关系的点
    {
        int w=pp[u][j];
        if(vis[w]==1)//如果点已经被访问，就确认父节点是谁
        {
            ans=find(w);
        }
    }
}

建议拿着纸和笔跟着我的描述一起模拟！！

假设我们有一组数据 9个节点 8条边 联通情况如下：

1--2，1--3，2--4，2--5，3--6，5--7，5--8，7--9 即下图所示的树

设我们要查找最近公共祖先的点为9--8，4--6，7--5，5--3；

设f[]数组为并查集的父亲节点数组，初始化f[i]=i，vis[]数组为是否访问过的数组，初始为0;

下面开始模拟过程：

取1为根节点，往下搜索发现有两个儿子2和3；

先搜2，发现2有两个儿子4和5，先搜索4，发现4没有子节点，则寻找与其有关系的点；

发现6与4有关系，但是vis[6]=0，即6还没被搜过，所以不操作；

发现没有和4有询问关系的点了，返回此前一次搜索，更新vis[4]=1；

表示4已经被搜完，更新f[4]=2，继续搜5，发现5有两个儿子7和8;

先搜7，发现7有一个子节点9，搜索9，发现没有子节点，寻找与其>有关系的点；

发现8和9有关系，但是vis[8]=0,即8没被搜到过，所以不操作；

发现没有和9有询问关系的点了，返回此前一次搜索，更新vis[9]=1；

表示9已经被搜完，更新f[9]=7，发现7没有没被搜过的子节点了，寻找>与其有关系的点；

发现5和7有关系，但是vis[5]=0，所以不操作；

发现没有和7有关系的点了，返回此前一次搜索，更新vis[7]=1；

表示7已经被搜完，更新f[7]=5，继续搜8，发现8没有子节点，则寻找与其有关系的点；

发现9与8有关系，此时vis[9]=1，则他们的最近公共祖先为>find(9)=5；

(find(9)的顺序为f[9]=7-->f[7]=5-->f[5]=5 return 5;)

发现没有与8有关系的点了，返回此前一次搜索，更新vis[8]=1；

表示8已经被搜完，更新f[8]=5，发现5没有没搜过的子节点了，寻找与其有关系的点；

发现7和5有关系，此时vis[7]=1，所以他们的最近公共祖先为find(7)=5；

(find(7)的顺序为f[7]=5-->f[5]=5 return 5;)

又发现5和3有关系，但是vis[3]=0，所以不操作，此时5的子节点全
部搜完了；

返回此前一次搜索，更新vis[5]=1，表示5已经被搜完，更新f[5]=2；

发现2没有未被搜完的子节点，寻找与其有关系的点；

又发现没有和2有关系的点，则此前一次搜索，更新vis[2]=1；

表示2已经被搜完，更新f[2]=1，继续搜3，发现3有一个子节点6；

搜索6，发现6没有子节点，则寻找与6有关系的点，发现4和6有关系；

此时vis[4]=1，所以它们的最近公共祖先为find(4)=1;

(find(4)的顺序为f[4]=2-->f[2]=2-->f[1]=1 return 1;)

发现没有与6有关系的点了，返回此前一次搜索，更新vis[6]=1，表示6已>经被搜完了；

更新f[6]=3，发现3没有没被搜过的子节点了，则寻找与3有关系的点；

发现5和3有关系，此时vis[5]=1，则它们的最近公共祖先为>find(5)=1；

(find(5)的顺序为f[5]=2-->f[2]=1-->f[1]=1 return 1;)

发现没有和3有关系的点了，返回此前一次搜索，更新vis[3]=1；

更新f[3]=1，发现1没有被搜过的子节点也没有有关系的点，此时可以退出整个dfs了。

经过这次dfs我们得出了所有的答案，有没有觉得很神奇呢？是否对Tarjan算法有更深层次的理解了呢？

#include<iostream>
#include<cstdio>
#include<string.h>
#include<vector>
#define MAN 10005
using namespace std;
vector<int> ve[MAN];
vector<int> pp[MAN];
int fa[MAN],vis[MAN];
int ans,n;
int find(int x)
{
    if(x==fa[x])
    {
        return x;
    }
    else
    {
        return find(fa[x]);
    }
}
void ouin(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
    {
        fa[y]=x;
    }
}
void init( )
{
    for(int i=0;i<=n;i++)
    {
        fa[i]=i;
        ve[i].clear();
        pp[i].clear();
        vis[i]=0;
    }
}
void dfs(int u)
{
    vis[u]=1;
    for(int i=0;i<ve[u].size();i++)
    {
        int v=ve[u][i];
        dfs(ve[u][i]);
        ouin(u,ve[u][i]);
    }
    for(int j=0;j<pp[u].size();j++)
    {
        int w=pp[u][j];
        if(vis[w]==1)
        {
            //cout<<w<<endl;
            ans=find(w);
        }
    }
}
int main( )
{
    int t,x,y,a,b;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        init( );
        for(int i=1;i<=n-1;i++)
        {
            scanf("%d%d",&x,&y);
            ve[x].push_back(y);
            vis[y]=1;
        }
        scanf("%d%d",&a,&b);
        pp[a].push_back(b);
        pp[b].push_back(a);
        for(int i=1;i<=n;i++)
        {
            if(vis[i]==0)
            {
                memset(vis,0,sizeof(vis));
                dfs(i);
                break;
            }
        }
        // for(int i=1;i<=n;i++)
        // {
        //  cout<<fa[i]<<" ";
        // }
        cout<<endl;
        printf("%d\n",ans);
    }
    return 0;
}

RMQ与LCA

参考大佬传送门https://www.cnblogs.com/scau20110726/archive/2013/05/26/3100812.html
首先阐述一下RMQ怎么能和LCA扯上关系呢？现在思考一下，最近公共祖先求的是两点的最近的公共祖先。而祖先肯定是在两者上面的，那这么说，祖先的深度是小的。那这样就可以将RMQ与最近公共祖先联系起来了。但是要怎样遍历一棵树才可以将它的深度分清楚呢。
先来操作一波


上面是什么遍历呢。可以看出它是先根，再左再右。这样能保证根一定在前面被遍历。那这样的话根的深度就比子节点小了。
还要注意，这个遍历的特点哦！有回溯的过程哦！保证根节点都在两者之间。
分清遍历序号和节点序号(如图中的A，B......)哦!
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
const int M=20010;
int n;
int head[M],cnt=0;
int vis[M],tot;//tot遍历的序号
int depth[M],tra[M];//depth数组记录每次遍历的深度，tra数组记录的是遍历的节点序号
int dp[M][25];//从第i个连续的2^j深度小的遍历序号
int first[M];//记录每个节点序号第一次出现的遍历序号
struct node
{
    int v,nxt;
}edge[M];
void add(int x,int y)
{
    edge[++cnt].nxt=head[x];
    edge[cnt].v=y;
    head[x]=cnt;
}
void dfs(int x,int deth)
{
    vis[x]=1;
    tra[++tot]=x;//记录节点序号
    depth[tot]=deth;//记录每次遍历序号对应的深度
    first[x]=tot;//记录节点序号第一次出现的遍历序号tot
    for(int i=head[x];i!=-1;i=edge[i].nxt)
    {
        int u=edge[i].v;
        if(!vis[u])
        {
            dfs(u,deth+1);
            tra[++tot]=x;//遍历回溯
            depth[tot]=deth;//每个遍历序号的深度
        }
    }
}
int find(int x,int y)
{
    if(depth[x]<depth[y])//深度小的，返回遍历序号
    {
        return x;
    }
    else
    {
        return y;
    }
    
}
void ST(int n)
{
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=i;
    }
    for(int j=1;j<=24;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            dp[i][j]=find(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
        }
    }
}
int RMQ(int i,int j)
{
    int k=log2(j-i+1.0);
    return find(dp[i][k],dp[j-(1<<k)+1][k]);
}
int LCA(int u,int v)
{
    int x=first[u];
    int y=first[v];
    if(x>y)
    {
        swap(x,y);
    }
    int res=RMQ(x,y);//得到了深度最小的遍历序号了
    return tra[res];//返回节点序号
}
int main( )
{
    int t,n,x,y;
    cin>>t;
    while(t--)
    {
        tot=cnt=0;
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        cin>>n;
        for(int i=1;i<n;i++)
        {
            cin>>x>>y;
            add(x,y);
            vis[y]=1;
        }
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])//寻找根节点开始遍历
            {
                memset(vis,0,sizeof(vis));
                dfs(i,1);
                //cout<<i<<" i "<<endl;
                break;
            }
        }
        ST(2*n-1);
        // for(int i=1;i<=2*n-1;i++)
        // {
        //     cout<<tra[i]<<" ";
        // }
        //cout<<endl;
        cin>>x>>y;
        cout<<LCA(x,y)<<endl;
    }
    return 0;
}

倍增

倍增中的ST函数的意思是： 在ST算法中，我们维护了一个数组DP[i][j]，表示的是以下标为i为起点的长度为2^j的序列的信息。然后用动态规划的思想求出整个数组。刚才在上面说我们求LCA时一次要跳2的幂次方层，这就与DP数组中下标j 的定义不谋而合了。所以我们定义倍增法中的DP[i][j]存放的是：结点 i 的向上2^j 层的祖先。例如下面这个图：


DP[4][1]=1；结点4的向上2^1=2层的祖先是结点1。
DP[10][1]=2；结点10的向上2^1=2层的祖先是结点2。
特别地，DP[6][0]=3，结点6的向上2^0=1层的祖先是3，即6的父节点。而这一现象正好可以当做DP的初始条件。DP[i][0]为i的父节点。下面写出递推式：
DP[i][j] = DP[ DP[i][j-1] ] [j-1]，如何理解这个递推式呢？DP[i][j-1]是结点i往上跳2^{(j-1)}层的祖先，那我们就在跳到这个结点的基础上，再向上跳2^{(j-1)}层，这样就相当于从结点i，先跳2^{(j-1)}层，跳到DP[i][j-1]得到2^{(j-1)}祖先节点x,节点x（DP[i][j-1]）再跳2^{(j-1)}层，最后还是到达了2^j层
DP[10][1]=DP[DP[10][1-1]][1-1]--->DP[5][0]-->2,DP[10][0]表示的是节点10跳1层到节点5，节点5在跳一层就不是节点10跳了2层了。。。。。

再看这副图：
DP[15][0]=9;DP[15][1]=5;DP[15][2]=2;
DP[5][0]=4;DP[5][1]=2;
DP[15][2]=DP[DP[15][1]][1]=2

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int deth[11000];
int dp[11000][25];
int vis[11000];
int head[11000];
int cnt;
struct node
{
    int v,nxt;
}edge[11000];
void add(int x,int y)
{
    edge[++cnt].nxt=head[x];
    edge[cnt].v=y;
    head[x]=cnt;
}
void dfs(int x,int u,int dep)
{
    dp[x][0]=u;
    deth[x]=dep;
    for(int i=head[x];i!=-1;i=edge[i].nxt)
    {
        int v=edge[i].v;
        dfs(v,x,dep+1);
    }
}
void Mul(int n)
{
    for(int j=1;(1<<j)<=n;j++)
    {
        for(int i=1;i<=n;i++)
        {
            dp[i][j]=dp[dp[i][j-1]][j-1];
        }
    }
}
int LCA(int x,int y)
{
    if(deth[x]<deth[y])//保证x的深度大
    {
        swap(x,y);
    }
    for(int i=24;i>=0;i--)
    {
        if(deth[x]-(1<<i)>=deth[y])//保证x的深度小于等于y，否则可能把最近公共祖先跳过了
        {
            x=dp[x][i];
        }
    }
    if(x==y)//两者其中之一是对方的祖先
    {
        return x;
    }
    for(int i=24;i>=0;i--)//处于相同层，于是一直往上跳
    {
        if(dp[x][i]!=dp[y][i])//处于相同层，于是一直往上往下跳,直到两者祖先不相同，开始分支x与y再向上跳
                             //如图中的节点9与节点10，直到i=0时两者才不相同，于是x=5,y=6，再返回x节点的1层祖先。图中的节点9与节点14，i=2时祖先相同，但是i=1后面的不相同,于是x=4,y=7;i=0,但是4的1层祖先是2，7的1层祖先是3，所以x=2,y=3;返回节点2的1层祖先
        {
            x=dp[x][i];
            y=dp[y][i];
        }
    }
    return dp[x][0];//dp[y][0]
}
int main( )
{
    int t,n,x,y;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cnt=0;
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<n;i++)
        {
            cin>>x>>y;
            add(x,y);
            vis[y]=1;
        }
        for(int i=1;i<=n;i++)
        {
            if(vis[i]==0)
            {
                //cout<<i<<endl;
                dfs(i,-1,0);
                break;
            }
        }
        Mul(n);
        cin>>x>>y;
        cout<<LCA(x,y)<<endl;
    }
    return 0;
}
上一篇下一篇

猜你喜欢

热点阅读