从哪里跌倒从哪里爬起来,明年我会再来见你的,亲爱的百度HR。艰苦的路从LCA开始。如何求一棵树中节点的最近公共先祖,Tarjan算法,复杂度O(N)网上说O(N+E)有点不太能理解,基于深度优先搜索和并查集。
算法基本思路,从根开始深度遍历,经过任意一个节点,都要以该节点为根建立一个集合,随着深度遍历的进行,当一个节点的子节点标记被访问时(即该子节点的所有子节点都标记被访问),将该节点所在的集合和该子节点所在的集合合并,并以该节点为根。上述的过程随着深度遍历递归进行。
遍历的过程同时也是查询的过程,当遍历到的节点是其中查询的节点中的一个,判断另一个节点是否已经被访问,如果被标记访问,那LCA就是被访问节点所在集合的根节点。
算法基本思路,从根开始深度遍历,经过任意一个节点,都要以该节点为根建立一个集合,随着深度遍历的进行,当一个节点的子节点标记被访问时(即该子节点的所有子节点都标记被访问),将该节点所在的集合和该子节点所在的集合合并,并以该节点为根。上述的过程随着深度遍历递归进行。
遍历的过程同时也是查询的过程,当遍历到的节点是其中查询的节点中的一个,判断另一个节点是否已经被访问,如果被标记访问,那LCA就是被访问节点所在集合的根节点。
#include<iostream> #include<string.h> using namespace std; class node { public: int key; bool visit; node* left; node* right; node() { key=-1; visit=false; } ~node() { if(this->left!=NULL) { delete this->left; this->left=NULL; } if(this->right!=NULL) { delete this->right; this->right=NULL; } //delete this; } node(int key) { this->key=key; this->left=NULL; this->right=NULL; } }; class btree { public: node* root; node* list[10000]; btree() { this->root=NULL; } ~btree() { delete root; } void insert(node* p) { if(p->key<=0) return; if(p->key%2==1) list[(p->key)/2+(p->key)%2-1]->left=p; if(p->key%2==0) list[(p->key)/2+(p->key)%2-1]->right=p; return; } }; class union_find_set { public: int anc; int father[10000]; union_find_set() { for(int i=0;i<10000;i++) this->father[i]=-1; } int getFather(int v) { if(this->father[v]==v) { return v; } else { //getFather(this->father[v]); return getFather(father[v]); } } bool same(int x,int y) { return (getFather(x)==getFather(y)); } bool judge(int x,int y) { int fx,fy; fx=getFather(x); fy=getFather(y); if(fx==fy) false; else { father[fx]=fy; return true; } } }; union_find_set ufset; int visit[10000]; int result; void dfs(node* p,int a,int b) { ufset.father[p->key]=p->key; if(a==p->key) { if(visit[b]==1) result=ufset.getFather(b); } if(b==p->key) { if(visit[a]==1) result=ufset.getFather(a); } if(p->left!=NULL) { dfs(p->left,a,b); ufset.judge(p->left->key,p->key); } if(p->right!=NULL) { dfs(p->right,a,b); ufset.judge(p->right->key,p->key); } visit[p->key]=1; } void getLCA(node* p,int a,int b) { memset(visit,0,sizeof(visit)); dfs(p,a,b); } int main() { int a,b; btree* tree=new btree; for(int i=0;i<=14;i++) { node* n=new node(i); tree->list[i]=n; tree->insert(n); } tree->root=tree->list[0]; //cout<<tree->list[8]->left->key<<endl; while(cin>>a>>b) { for(int i=0;i<10000;i++) ufset.father[i]=-1; getLCA(tree->root,a,b); for(int i=0;i<15;i++) { //cout<<"father["<<i<<"]="<<ufset.father[i]<<endl; } //cout<<ufset.father[0]<<endl; //cout<<ufset.getFather(3)<<endl; cout<<result<<endl; } delete tree; return 0; }
发表评论
-
图的割点tarjan---zoj_1119
2011-10-24 23:00 1235http://acm.zju.edu.cn/on ... -
BFS与双向BFS---zoj_1505
2011-10-09 17:14 1647http://acm.zju.edu.c ... -
静态treap+线段树---zoj_2112
2011-09-29 23:06 1712http://acm.zju.edu ... -
NIM博弈游戏,SG函数---zoj_3084,zoj_2083
2011-09-23 23:00 1321Nim游戏是两个人进行的游戏有如下规则: ... -
多重背包--zoj_2156
2011-09-14 11:10 867首先介绍经典的三种背包问题,0-1背包,完全 ... -
模式串匹配---KMP
2011-08-31 20:49 1282朴素的的模式串匹配算法通常要在向前移动文本指针 ... -
八数码问题(A*&&双向BFS)---zoj_1217
2011-08-30 22:13 1672题目地址:http://acm.zju.edu.cn/onli ... -
ac自动机以及它上面的DFA
2011-08-08 23:04 2483AC自动机(Aho-Corasick)主要用 ... -
二分图最大匹配(匈牙利算法)--zoj1516,1525,2223
2011-07-20 22:36 1189二分图G(E,V)将点集合V分成两个部分L,R ... -
网络最大流(EK)---zoj_1734
2011-07-19 16:34 2136网络最大流是图论中的一个典型问题,为了精确的定 ... -
trie和前缀检查---zoj_2876
2011-07-13 23:03 870trie树是一种多叉树,广泛用于字典检索。如 ... -
位图bitmap
2011-07-13 21:08 916bitmap是一种广泛使用的数据结构,主要用在 ... -
LAC和RMQ的转化---zoj_3195
2011-07-12 22:35 1077我擦。。纠结了好久啊,从SF到TLE,先总结2 ... -
LAC的tarjan(离线)算法---zoj_1141
2011-07-08 17:52 1662LCA就不解释了,这里主要再次复习一下LC ... -
笛卡尔树以及treap---zoj_2243
2011-07-07 15:52 2846zoj_2243笛卡 ... -
线段染色,矩形切割,离散化---zoj_2301,zoj_1128
2011-06-24 22:32 1369染色问题:在一维坐标轴上(最右端为M),有N ... -
线段树---zoj_1610
2011-06-22 21:06 753线段树是一种二叉树的拓展,在线段树每个节点中 ... -
快速排序(qsort)
2011-06-16 17:03 782快速排序是一种高效的非稳定排序,它的基本思路 ... -
斐波那契散列
2011-06-16 16:38 3082斐波那契散列法其实是一种特殊的乘法散列,先来看乘法 ... -
强连通分支(scc)---tarjan
2011-06-15 16:17 1285本文大量 ...
相关推荐
LCA 详解以及完整代码详细介绍了倍增法的原理以及Pascal的完整代码 很好很强大
LCA_树上差分讲解PPT 详细易懂 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!...
RMQ与LCA ACM必备RMQ与LCA ACM必备 RMQ与LCA ACM必备
日立LCA电气图纸(K3500490).pdf
关于RMQ和LCA的关系的知识,如何用RMQ和LCA的转换
c++写的Tarjan 的 LCA 算法,最近公共祖先算法,可供算法学习参考
用户数据的读取方法,如何对LCA265显示器传输数据。
LCA系统 DB2数据库 表 修改数据状态
LCA生命周期评价,LCA生命周期评价课件,LCA生命周期评价PPT
LCA 中文教程,内部资料--产品结构管理,还不错啊,可以看下
数据泄密(泄露)防护(Data leakage prevention, DLP),又称为“数据丢失防护”(Data Loss prevention, DLP),有时也称为“信息泄漏防护”(Information leakage prevention, ILP)。数据泄密防护(DLP)是通过一定的...
LCA词汇复杂度分析软件 跟官网一毛一样 可以做成本地接口
很详细的LCA与RMQ计算过程的图例演示,以及他们之间的转换
一个很经典的论文,关于slca的论文,现在关于查询方面的知识,好多都是基于slca的
lca51仿真软件早期版本2.02版,不知是否有需要的。
SAS+proc lca浅类别分析安装程序
Tarjan应用LCA
对于LCA问题,有不少解法,这儿提供了tarjan算法,这是一种离线算法,读入所有输入然后一并处理,并且利用并查集的思想,从根节点开始DFS,对每一个DFS的节点,先把他的父亲节点指向本身,没访问完一个子节点,然后...
算法学习
LCA系统中的数据状态控制以及数据升版操作规范