欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LCA最近公共祖先(tarjan离线)

程序员文章站 2024-03-22 17:24:22
...

求最近公共祖先的方法有三个:tarjan离线,倍增在线,RMQ。tarjan离线的方法理解起来较为简单。

一.Tarjan算法大致实现过程
  1. 先选择一个节点u为根节点,从根节点开始搜索。(标记u已访问过)
  2. 遍历该点u的所有儿子节点v,并标记v已访问过。
  3. 若v还有儿子节点,对v重复ii操作,否则进入下一操作。
  4. 把v合并到u上(并查集)。
  5. 把当前的点设为u,遍历与u有询问关系的节点v。
  6. 如果v在之前已经被访问过,那么u和v的最近公共祖先就是v通过并查集合并后的父亲节点(注意是合并后),即当前的find(v)

二.tarjan算法的伪代码:

Tarjan(u)           //根节点u  
{  
    for each(u,v)  
    {  
        Tarjan(v);  //v还有儿子节点  
        join(u,v);  //把v合并到u上  
        vis[v]=1;   //访问标记  
    }  
    for each(u,v)   //遍历与u有询问关系的节点v  
    {  
        if(vis[v])  
        {  
            ans=find(v);  
        }  
    }  
}  

三. Tarjan算法模拟

LCA最近公共祖先(tarjan离线)

还是原来的图,如图,图*有8个点,7条边,我们需要寻找最近公共祖先的点对为<3,5>,<5,6>,<2,7>,<6,7>

先做好初始化工作,开一个pre数组,记录父亲节点,初始化pre[i]=i;
再开一个vis数组,记录是否已经访问 (memset(vis,0,sizeof(vis)))

然后开始模拟整个过程

1.先取1为根节点, 发现其有两个子节点2和3,先搜索2,又发现2有两个子节点4和5,先搜索4,4也有两个子节点6和7,先搜索6,这时发现6没有子节点了,然后寻找与其有询问关系的节点,发现5和7均与6有询问关系,但都没被访问过。所以返回并标记vis[6]=1,pre[6]=4;

2.接着搜索7,发现7没有子节点,然后寻找与其有询问关系的节点,发现6与其有询问关系,且vis[6]=1,所以LCA(6,7)=find(6)=4。结束并标记vis[7]=1,pre[7]=4;

3.现在节点4已经搜完,且没有与其有询问关系的节点,vis[4]=1,pre[4]=2;

4.搜索5,发现其有子节点8,搜索8,发现8没有子节点,然后寻找与其有询问关系的节点,也没有,于是返回,且vis[5]=1,pre[8]=5;

5.节点5已经搜完,发现有两个与其有询问关系的节点6和7,且vis[6]=1,所以LCA(5,6)=find(6)=2;因为vis[7]=1,所以LCA(5,7)=find(7)=2;遍历完毕返回,标记vis[5]=1,pre[5]=2;

(find过程:pre[7]=4,pre[4]=2    ==》2 )

6.节点2已经搜完,发现有一个与其有询问关系的节点7,且vis[7]=1,故LCA(2,7)=find(7)=2。遍历完毕,标记vis[2]=1,pre[2]=1;

7.接着搜索3,没有子节点,发现有一个与其有询问关系的节点5,因为vis[5]=1,所以LCA(3,5)=find(5)=1;遍历结束,标记vis[3]=1,pre[3]=1;

(find过程:pre[5]=2,pre[2]=1   ==》1 )

8.这时返回到了节点1,它没有与之有询问关系的点了,且其pre[1]=1,搜索结束。

完成求最小公共祖先的操作。

四.Tarjan算法的代码


由于LCA的题目千变万化,下面给出最基础的模板(给出一系列边用邻接表保存,把询问也用邻接表保存,只求LCA,不维护其他值)


void Tarjan(int now)  
{  
    vis[now]=1;  
    for(int i=head1[now];i!=-1;i=e1[i].next)  
    {  
        int t=e1[i].t;  
        if(vis[t]==0)  
        {  
            Tarjan(t);  
            join(now,t);  
        }  
    }  
    for(int i=head2[now];i!=-1;i=e2[i].next)  
    {  
        int t=e2[i].t;  
        if(vis[t]==1)  
        {  
            e2[i].lca=find(t);  
            e2[i^1].lca=e2[i].lca;  
        }  
    }  
}  

五.例题:http://poj.org/problem?id=1330

就是 输入cas 后  有cas组数据 输入 n   再输入n-1 条边    之后输入x y  问x y的最近公共祖先是什么

裸的LCA:

代码:

#include<stdio.h>  
#include<vector>  
#include<string.h>  
using namespace std;  
#define Size 11111  //节点个数  
  
vector<int> node[Size],que[Size];  
int n,pare[Size],anse[Size],in[Size],rank[Size];  
  
int vis[Size];  
void init()  
{  
    int i;  
    for(i=1;i<=n;i++)  
    {  
        node[i].clear();  
        que[i].clear();  
        rank[i]=1;  
        pare[i]=i;///   
    }  
    memset(vis,0,sizeof(vis));  
    memset(in,0,sizeof(in));  
    memset(anse,0,sizeof(anse));  
       
}  
  
int find(int nd)//并查集操作  不解释  
{  
    return pare[nd]==nd?nd:pare[nd]=find(pare[nd]);  
}  
int Union(int nd1,int nd2)//并查集操作  不解释  
{  
    int a=find(nd1);  
    int b=find(nd2);  
    if(a==b) return 0;  
    else if(rank[a]<=rank[b])  
    {  
        pare[a]=b;  
        rank[b]+=rank[a];  
    }  
    else   
    {  
        pare[b]=a;  
        rank[a]+=rank[b];  
    }  
    return 1;  
  
}  
  
void LCA(int root)  
{  
    int i,sz;  
    anse[root]=root;//首先自成一个集合  
    sz=node[root].size();  
    for(i=0;i<sz;i++)  
    {  
           LCA(node[root][i]);//递归子树  
           Union(root,node[root][i]);//将子树和root并到一块   
         anse[find(node[root][i])]=root;//修改子树的祖先也指向root  
    }  
    vis[root]=1;  
    sz=que[root].size();  
    for(i=0;i<sz;i++)  
    {  
            if(vis[que[root][i]])  
            {  
                printf("%d\n",anse[find(que[root][i])]);///root和que[root][i]所表示的值的最近公共祖先  
                return ;  
            }  
    }  
     return ;  
}  
  
int main()  
{  
    int cas,i;  
    scanf("%d",&cas);  
    while(cas--)  
    {  
        int s,e;  
        scanf("%d",&n);  
        init();  
        for(i=0;i<n-1;i++)  
        {  
            scanf("%d %d",&s,&e);  
            if(s!=e)  
            {  
                node[s].push_back(e);  
               // node[e].push_back(s);  
                in[e]++;  
            }  
        }  
        scanf("%d %d",&s,&e);  
        que[s].push_back(e);  
        que[e].push_back(s);  
        for(i=1;i<=n;i++)  if(in[i]==0) break;//寻找根节点  
    //  printf("root=%d\n",i);  
        LCA(i);  
    }  
    return 0;  
}  
参考:

http://blog.csdn.net/hnust_xiehonghao/article/details/9109295

http://blog.csdn.net/lw277232240/article/details/77017517

http://blog.csdn.net/my_sunshine26/article/details/72717112