Menu
Article ACM

算法学习————LCA问题的Tarjan算法

NodeKey

NodeKey

• 2 min read

LCA 即 最近公共祖先

对于一棵有根树，就会有父亲结点，祖先结点。

<code class="language-null">     0
     |
     1
    /  \  
  2    3
       /  \
     4    5

举几个例子 如图 这棵树的所有节点的根节点都是 0
但是
4 5 的LCA 是3
2 5的LCA 是1
1 3的LCA 是1

这里要介绍的 求最近公共祖先的算法是 Tarjan 算法 算法的核心思想在于 我们从一棵树的根节点开始向下深搜 当我们回溯的时候 我们才把两个集合合并 并更新根节点

这就意味着 对于一个节点 我们只有访问过他的所有子节点和他本身之后才更新他的根节点 我再简单点说 这样操作就实现了从叶子节点不断向上更新根节点 如果我们再更新之前完成记录LCA的操作 一切并迎刃而解

附上伪代码

<code class="language-null">//parent为并查集，FIND为并查集的查找操作  
//QUERY为询问结点对集合  
//TREE为基图有根树  
Tarjan(u)  
    visit[u] = true  
        for each (u, v) in QUERY  
            if visit[v]  
                ans(u, v) = FIND(v)  
            for each (u, v) in TREE      
                if !visit[v]  
                    Tarjan(v)  
                parent[v] = u

附上一个小题目 poj 1470

题意 多次查询后 问你LCA节点的次数

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>

using namespace std;
const int maxn=905;
struct node
{
    int v;
    node* nxt;
};
node* head1[maxn];
node* head2[maxn];
node edge1[maxn<<1],edge2[500005];
int root[maxn],num[maxn];
bool vis[maxn],flag[maxn];
int n,idx1,idx2,m;

void init()
{
    for(int i=0;i<=n;i++)
    {
        head1[i]=head2[i]=0;
        num[i]=vis[i]=flag[i]=0;
    }
    idx1=idx2=0;
}

int fin(int x)
{
    if(root[x]==x) return x;
    return root[x]=fin(root[x]);
}

void Tarjan(int u)
{
    root[u]=u;
    vis[u]=true;

    for(node* p=head2[u];p;p=p->nxt)
        if(vis[p->v])
            num[fin(p->v)]++;

    for(node* p=head1[u];p;p=p->nxt)
        if(!vis[p->v])
        {
            Tarjan(p->v);
            root[p->v]=u;
        }
}

void add(int u,int v,node* head[],node edge[],int& idx)
{
    edge[idx].v=v;
    edge[idx].nxt=head[u];
    head[u]=edge+idx++;

    edge[idx].v=u;
    edge[idx].nxt=head[v];
    head[v]=edge+idx++;
}

int main()
{
    int numm,u,v;
    while(scanf("%d",&n)!=EOF)
    {
        init();
        for(int i=1;i<=n;i++)
        {
            scanf("%d:(%d)",&u,&numm);
            while(numm--)
            {
                scanf(" %d",&v);
                flag[v]=true;
                add(u,v,head1,edge1,idx1);
            }
        }
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf(" (%d %d)",&u,&v);
            add(u,v,head2,edge2,idx2);
        }
        for(int i=1;i<=n;i++)
            if(flag[i]==0)
            {
                Tarjan(i);
                break;
            }
        for(int i=1;i<=n;i++)
            if(num[i]) printf("%d:%d\n",i,num[i]);
    }
    return 0;
}
Share