首页 > 编程语言 > 详细

LCA—Tarjan算法

时间:2018-07-18 20:05:18      阅读:46      评论:0      收藏:0      [点我收藏+]

标签:就是   scan   优先   也有   开始   特点   truct   几种操作   深度   

#include<bits/stdc++.h>
using namespace std;
const int SIZE =50010;
struct edge
{
    int next,y,v;
}e[SIZE*2];
int to[SIZE];
int fa[SIZE],d[SIZE],v[SIZE],lca[SIZE],ans[SIZE];
vector<int> query[SIZE],query_id[SIZE];
int T,n,m,tot,t,len=0;
void insert(int xx,int yy,int vv)
{
    e[++len].next=to[xx];
    to[xx]=len;
    e[len].y=yy;
    e[len].v=vv;
}
void add_query(int x,int y,int id)
{
    query[x].push_back(y),query_id[x].push_back(id);
    query[y].push_back(x),query_id[y].push_back(id);
}
int getf(int x)
{
    if(x==fa[x]) return x;
    return fa[x]==getf(fa[x]);
}
void tarjan(int x)
{
    v[x]=1;
    for(int i=to[x]; i;i=e[i].next)
    {
        int y=e[i].y;
        if(v[y]) continue;
        d[y] = d[x] + e[i].v;
        tarjan(y);
        fa[y]=x;
    }
    for(int i=0;i < query[x].size();i++)
    {
        int y=query[x][i],id=query_id[x][i];
        if(v[y]==2)
        {
            int lca = getf(y);
            ans[id]=min(ans[id],d[x]+d[y]-2*d[lca]);
        }
    }
    v[x]=2;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            to[i]=0; fa[i]=i; v[i]=0;
            query[i].clear(),query_id[i].clear();
        }
        tot = 0;
        for(int i=1;i<n;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            insert(x,y,z);
            insert(y,x,z);
        }
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(x==y)    ans[i]=0;
            else{
                add_query(x,y,i);
                ans[i]= 1<<30;
            }
        }
        tarjan(1);
        for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
    }
}

向上标记法

从x向上走到根节点,并标记所有经过的节点。

从y向上走到根节点,当第一次遇到已标记的节点,就找到了LCA(x,y).

对于每个询问,向上标记法的时间复杂度为O(n).m个询问时间复杂度则为O(nm).

Tarjan 算法

Tarjan是使用并查集对“向上标记法”的优化,需要将m个询问一次性输入,重新组织查询处理顺序,统一计算,最后统一输出。时间复杂度为O(n+m)。

思路:进入一个节点x的深搜,把整个树的一部分看作以节点x为根节点的小树,再搜索其他节点。每搜索完一个节点之后,如果该点和另一个已搜索完点为需要查询LCA的点,则这两点的LCA为另一个点现在的祖先。

回顾一波深度优先遍历(DFS)

关于树的DFS序

树的DFS序的特点就是对于每个节点恰好出现两次。

深度优先遍历,树中节点分三类:

  1. 已经访问完毕并且回溯的节点,在节点上标记一个整数2.
  2. 已经开始递归,但尚未回溯的节点。这些节点就是当前节点正在访问的节点x以及x的祖先。在这些节点上标记一个整数1.
  3. 对于尚未访问的节点。这些节点没有标记。

具体操作:

  1. 任选一个点为根节点,从根节点开始遍历该点x的所有子节点y,并标记已被访问。
  2. 如果y也有子节点,重复操作二,否则合并y到x上。
  3. 寻找与当前点x有询问关系的点y。因为是离线算法,所以将需要从询问找出与当前点有询问关系的点,即为离线做法的特点。
  4. 如果找出来的y已经被访问过了,则可以确认x和y的最近公共祖先为y在并查集中的代表元素。                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  

注意:Tarjan算法是离线算法,若题目强制在线(如针对几种操作,每一次求LCA操作后都要求输出答案),这时候Tarjan就不再适用。

【HDU2586】

题意: 将n个点用n-1条边相连,m次询问a,b两个点之间的距离。

分析:这就是一道LCA的板子题。明显可用离线算法Tarjan做。

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          

                       

LCA—Tarjan算法

标签:就是   scan   优先   也有   开始   特点   truct   几种操作   深度   

原文:https://www.cnblogs.com/ve-2021/p/9332036.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号