对于有根树 T 的两个结点 u,v, 最近公共祖先 x=LCA(u,v) 表示一个结点 x, 满足 x 是 u,v 的祖先且 x 的深度尽可能大.
如图, 根据定义可以看出 14 和 15 的最近公共祖先是 10, 15 和 16 的最近公共祖先是 1, 6 和 5 的最近公共祖先是 5......
假如我要求 14 和 16 的最近公共祖先, 要怎么做呢?
最暴力的做法, 就是先看 14 和 16 在不在同一层, 如果他们不在同一层, 那么较深的那个点往上爬 (即距离根较远的那个点)
一直爬, 爬到两点的深度一样
当两点深度一样时, 判断他们是否在同一个点上, 如果不是, 则两个点同时往上爬, 直到这两个点是同一个点
显然, 这么做一般来说都是不行的.
下面介绍倍增法 (图是用 vector 存的)
既然一步一步往上爬太慢了, 那就一次爬远一点
我们预处理一个数组 fa[x] [i] 使游标快速移动, 大幅度减少跳转次数.
fa[x] [i] 表示 点 x 的第 2^i 个祖先
拿上图来说, fa[15] [0] 就是点 15 的第 2^0 个祖先, 即 12(fa[15] [0] =12)
fa[15] [1] 就是点 15 的第 2^1 个祖先, 即 10(fa[15] [1] =10)
fa[15] [2] 就是点 15 的第 2^2 个祖先, 即 5(fa[15] [2] =5)
怎么预处理出这个数组呢? 我们观察上图, 15 的第一个祖先是 12,12 的第一个祖先是 10
即 fa[15] [0] =12 fa[12] [0] =10
而 15 的第二个祖先是 10, 和 12 的第一个祖先是一样的
fa[15] [1] =10
也就是说, 对于点 15 来说, 15 的第二个祖先就是 15 的第一个祖先的第一个祖先 (点 12 的第一个祖先)
用数组表示是 fa[15][1]=fa[ fa[15][0] ][ 0 ];
即 fa[15][1]=fa[12][0]
推广到第 2^i 个祖先: 递推式: fa[rt][i]=fa[fa[rt][i-1]][i-1];(rt 为当前节点)
预处理代码:(depth 数组存的是当前节点的深度)
- void dfs(int f,int rt )//rt 是当前节点, f 是当前节点的父亲
- {
- depth[rt]=depth[f]+1;
- fa[rt][0]=f;
- for(int i=1;i<20;++i)// 自己估计 i 的范围
- fa[rt][i]=fa[fa[rt][i-1]][i-1];
- for(int i=0;i<E[rt].size();++i)// 用 vector 存的图, 遍历当前节点的每一个孩子
- dfs(rt,E[rt][i]);
- }
下一个问题是, 游标移动到哪里合适?
我们的原则是, 先让两个点的深度一致
然后, 让两个点同时跳相同的步数
1. 如果跳出根以外了, 就不跳
2. 如果跳到的点是相同的点, 也不跳 (不一定是最近的公共祖先)
不是以上两种情况, 就跳
举个栗子, 如图:
假如我们问 14 和 15 的 lca 是哪个点
按照规则
我们先让 14 和 15 在同一层上 (深度一致)
14 跳到了 13
然后, 我们看跳多少步合适, 如果 i=3, 即 2^3=8 步, 发现已经跳出根以外了, 不跳
再看 i=2, 2^2=4,13 和 15 的第四个祖先都是 5, 不跳
再看 i=1, 即跳 2 步, 发现都是 10, 不跳
再看 i=0, 跳一步, 13 跳一步到 11,15 跳一步到 12, 两个点不相同, 可以跳
此时第一遍循环结束, 判断这两个点的第一个祖先是不是同一个点
如果是, 则找到了
如果不是, 那就继续进行循环
用图表示:
第一步是 14 跳到 13
第二步是 13 跳到 11,15 跳到 12
发现 11 和 12 的第一个祖先都是 10, 找到答案, 结束循环 (时间是 log 级别的)
代码:
- int lca(int x,int y)// 找 x 和 y 的最近公共祖先
- {
- if(depth[x]<depth[y])// 调整 x 的深度大一些
- swap(x,y);
- while(depth[x]!=depth[y])// 使 x 和 y 的深度一致
- {
- for(int i=9;i>=0;--i){// 初始常数自己根据问题进行调整
- if(depth[x]-(1<<i)>=depth[y])
- x=fa[x][i];
- }
- }
- if(x==y) return x;
- while(fa[x][0]!=fa[y][0])// 当 x 和 y 的第一位祖先都一样时退出循环
- {
- for(int i=9;i>=0;--i){
- // 如果没有出界而且两点的祖先不一样, 就跳
- if(fa[x][i]!=0&&fa[x][i]!=fa[y][i])
- x=fa[x][i],y=fa[y][i];
- }
- }
- return fa[x][0];
- }
- View Code
代码自己写的, 有点丑, 网上的没看懂....
下面给出测试代码和样例, 大家可以去试一试, 样例就是第一幅图
- #include <iostream>
- #include <queue>
- #include <vector>
- #include <stdio.h>
- using namespace std;
- vector<int> E[20];
- int depth[20];
- int fa[20][20];
- void dfs(int f,int rt )
- {
- depth[rt]=depth[f]+1;
- fa[rt][0]=f;
- for(int i=1;i<20;++i)
- fa[rt][i]=fa[fa[rt][i-1]][i-1];
- for(int i=0;i<E[rt].size();++i)
- dfs(rt,E[rt][i]);
- }
- int lca(int x,int y)
- {
- if(depth[x]<depth[y])// 调整左边深
- swap(x,y);
- while(depth[x]!=depth[y])
- {
- for(int i=9;i>=0;--i){
- if(depth[x]-(1<<i)>=depth[y])
- x=fa[x][i];
- }
- }
- if(x==y) return x;
- while(fa[x][0]!=fa[y][0])
- {
- for(int i=9;i>=0;--i){
- if(fa[x][i]!=0&&fa[x][i]!=fa[y][i])
- x=fa[x][i],y=fa[y][i];
- }
- }
- return fa[x][0];
- }
- int main()
- {
- int l,r;
- for(int i=1;i<=15;++i){
- cin>>l>>r;
- E[l].push_back(r);
- }
- dfs(0,1);
- int a,b,t=100;
- while(t--)
- {
- cin>>a>>b;
- cout<<lca(a,b)<<endl;
- }
- return 0;
- }
- /*
- 输入图:
- 1 2
- 2 4
- 4 5
- 5 6
- 5 7
- 7 10
- 10 11
- 10 12
- 11 13
- 12 15
- 13 14
- 1 3
- 3 8
- 8 9
- 9 16
- */
- View Code
来源: http://www.bubuko.com/infodetail-3034600.html