首页 > 代码库 > 倍增法求LCA
倍增法求LCA
倍增法求LCA
LCA(Least Common Ancestors)的意思是最近公共祖先,即在一棵树中,找出两节点最近的公共祖先。
倍增法是通过一个数组来实现直接找到一个节点的某个祖先,这样我们就可以在O(logn)的时间内求出求出任意节点的任意祖先。
然后先把两个节点中转化为深度相同的节点,然后一起向上递增,知道找到相同的节点,该节点就是这两个节点的最近公共祖先。
代码实现:
1 #include<cstdio> 2 #include<iostream> 3 #define N 42000 4 using namespace std; 5 int next[N],to[N],head[N],num,deep[N],father[N][21],n,m,p,a,b,c; 6 void add(int false_from,int false_to){ 7 next[++num]=head[false_from]; 8 to[num]=false_to; 9 head[false_from]=num; 10 } 11 void dfs(int x){ 12 deep[x]=deep[father[x][0]]+1; 13 for(int i=0;father[x][i];i++) 14 father[x][i+1]=father[father[x][i]][i]; 15 for(int i=head[x];i;i=next[i]) 16 if(!deep[to[i]]){ 17 father[to[i]][0]=x; 18 dfs(to[i]); 19 } 20 } 21 int lca(int x,int y){ 22 if(deep[x]>deep[y]) 23 swap(x,y); 24 for(int i=20;i>=0;i--) 25 if(deep[father[y][i]]>=deep[x]) 26 y=father[y][i]; 27 if(x==y) 28 return y; 29 for(int i=20;i>=0;i--) 30 if(father[y][i]!=father[x][i]){ 31 y=father[y][i]; 32 x=father[x][i]; 33 } 34 return father[x][0]; 35 } 36 int main(){ 37 scanf("%d%d%d",&n,&m,&p); 38 for(int i=1;i<n;++i){ 39 scanf("%d%d",&a,&b); 40 add(a,b); 41 add(b,a); 42 } 43 dfs(p); 44 for(int i=1;i<=m;++i){ 45 scanf("%d%d",&a,&b); 46 printf("%d ",lca(a,b)); 47 } 48 return 0; 49 }
倍增法求LCA
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。