专栏首页mlTarjan--LCA算法的个人理解即模板

Tarjan--LCA算法的个人理解即模板

tarjan---LCA算法的步骤是(当dfs到节点u时):

  实际:  并查集+dfs

具体步骤: 1 在并查集中建立仅有u的集合,设置该集合的祖先为u 1 对u的每个孩子v:    1.1 tarjan之    1.2 合并v到父节点u的集合,确保集合的祖先是u 2 设置u为已遍历 3 处理关于u的查询,若查询(u,v)中的v已遍历过,则LCA(u,v)=v所在的集合的祖先。

举例子:

假设遍历完10的孩子,要处理关于10的请求了 取根节点到当前正在遍历的节点的路径为关键路径,即1-3-8-10 集合的祖先便是关键路径上距离集合最近的点 比如此时:     1,2,5,6为一个集合,祖先为1,集合中点和10的LCA为1     3,7为一个集合,祖先为3,集合中点和10的LCA为3     8,9,11为一个集合,祖先为8,集合中点和10的LCA为8     10,12为一个集合,祖先为10,集合中点和10的LCA为10 你看,集合的祖先便是LCA吧,所以第3步是正确的 道理很简单,LCA(u,v)便是根至u的路径上到节点v最近的点

此段话语来自sre="http://purety.jp/akisame/oi/TJU/"

模板:

  1 #include<iostream>
  2 #include<vector>
  3 using namespace std;
  4 
  5 const int MAX=10001;
  6 int father[MAX];
  7 int rank[MAX];
  8 int indegree[MAX];//保存每个节点的入度
  9 int visit[MAX];
 10 vector<int> tree[MAX],Qes[MAX];
 11 int ancestor[MAX];
 12 
 13 
 14 void init(int n)
 15 {
 16     for(int i=1;i<=n;i++)
 17     {
 18 
 19         rank[i]=1;
 20         father[i]=i;
 21         indegree[i]=0;
 22         visit[i]=0;
 23         ancestor[i]=0;
 24         tree[i].clear();
 25         Qes[i].clear();
 26     }
 27 
 28 }
 29 
 30 int find(int n)
 31 {
 32     if(father[n]==n)
 33         return n;
 34     else
 35         father[n]=find(father[n]);
 36     return father[n];
 37 }//查找函数,并压缩路径
 38 
 39 int Union(int x,int y)
 40 {
 41     int a=find(x);
 42     int b=find(y);
 43     if(a==b)
 44         return 0;
 45     //相等的话,x向y合并
 46     else if(rank[a]<=rank[b])
 47     {
 48         father[a]=b;
 49         rank[b]+=rank[a];
 50     }
 51     else
 52     {
 53         father[b]=a;
 54         rank[a]+=rank[b];
 55     }
 56     return 1;
 57 
 58 }//合并函数,如果属于同一分支则返回0,成功合并返回1
 59 
 60 
 61 void LCA(int u)
 62 {
 63     ancestor[u]=u;
 64     int size = tree[u].size();
 65     for(int i=0;i<size;i++)
 66     {
 67         LCA(tree[u][i]);
 68         Union(u,tree[u][i]);
 69         ancestor[find(u)]=u;
 70     }
 71     visit[u]=1;
 72     size = Qes[u].size();
 73     for(int i=0;i<size;i++)
 74     {
 75         //如果已经访问了问题节点,就可以返回结果了.
 76         if(visit[Qes[u][i]]==1)
 77         {
 78             cout<<ancestor[find(Qes[u][i])]<<endl;
 79             return;
 80         }
 81     }
 82 }
 83 
 84 
 85 int main()
 86 {
 87     int cnt;
 88     int n;
 89     cin>>cnt;
 90     while(cnt--)
 91     {
 92         cin>>n;;
 93         init(n);
 94         int s,t;
 95         for(int i=1;i<n;i++)
 96         {
 97             cin>>s>>t;
 98             tree[s].push_back(t);
 99             indegree[t]++;
100         }
101         //这里可以输入多组询问
102         cin>>s>>t;
103         //相当于询问两次
104         Qes[s].push_back(t);
105         Qes[t].push_back(s);
106         for(int i=1;i<=n;i++)
107         {
108             //寻找根节点
109             if(indegree[i]==0)
110             {
111                 LCA(i);
112                 break;
113             }
114         }
115     }
116     return 0;
117 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 干货 | 机器学习算法线上部署方法

    作者简介 潘鹏举,携程酒店研发 BI 经理,负责酒店服务相关的业务建模工作,主要研究方向是用机器学习实现业务流程自动化、系统智能化、效率最优化,专注于算法实践和...

    用户1292807
  • 新手必看的十种机器学习算法

    AI 研习社按:在神经网络的成功的带动下,越来越多的研究人员和开发人员都开始重新审视机器学习,开始尝试用某些机器学习方法自动解决可以轻松采集数据的问题。然而,在...

    AI研习社
  • 上交大卢策吾团队开源 AlphaPose, 在 MSCOCO 上稳超 Mask-RCNN 8 个百分点

    I 研习社消息,日前,上海交通大学卢策吾团队开源 AlphaPose。AlphaPose 是一个多人姿态估计系统,具有极高的精准度。 据卢策吾团队介绍, Alp...

    AI研习社
  • DeepMind 提出全新强化学习算法,教智能体从零开始学会控制

    AI 研习社按:对于智能体来说,从零开始,通过最少的知识学习复杂的控制问题是一个众所周知的挑战。日前,DeepMind 提出全新强化学习算法「调度辅助控制」(S...

    AI研习社
  • 个性化推荐沙龙 | 饿了么推荐系统的从0到1(含视频)

    本文来自陈一村在携程个性化推荐与人工智能Meetup上的分享。 陈一村 ,饿了么数据运营部资深算法工程师。2016年加入饿了么,现从事大数据挖掘和算法相关工作,...

    用户1292807
  • AI+BlockChain 区块链火之后,人工智能凉了吗? | AI 热译

    翻译 | 彭艳蕾 付腾 校对 | 崔跃辉 熊若鑫 字幕 | 凡江 整理 | 吴璇 2018 年伊始,区块链 (Blockchain) 成为全民...

    AI研习社
  • 无人驾驶工程师技术总结

    无人驾驶作为一项新兴技术,落地为产品需要大量算法、工程、产品贯通的AI全栈人才。笔者在最近一年招聘中发现,许多技术方向的同学对人工智能既爱又畏惧,一方面觉得这是...

    刘盼
  • 如何上手使用 Facebook 的开源平台 Detectron?

    不久前,Facebook 开源了用于物体识别的 CV 开发平台 Detectron,为广大研究人员们未来的新计算机视觉研究课题提供灵活、快速的模型实现和评估途...

    AI研习社
  • 八大排序算法

    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说...

    程序员互动联盟
  • 【专业技术】引擎算法探究

    在一些大型购物网站,我们常会看到一个功能叫“猜你喜欢”(或其它类似的名字),里面列出一些跟你买过商品相关的其它商品。网站的用户越多,或你在网站上购买的东西越多,...

    程序员互动联盟

扫码关注云+社区

领取腾讯云代金券