题目大意: 给你一棵含有 n 个结点的树, n-1 条边, 问两个结点的最近公共祖先是哪个节点.
普通做法
思路:
让两个结点到达同一深度, 再一起往上走, 到达同一结点即为最近公共祖先.
例: 3 和 7, 让 3 往上走到 16, 与 7 同一深度后, 再一起一步步往上走, 到达 4 时, 为同一个结点, 即为其最近公共祖先.
基本步骤:
1, 邻接表存图(这里用到的是 vector)
2,dfs 出各个结点的深度
3, 让深度较高的往上走, 走到同一深度
4, 两个结点一起往上走, 走到同一个结点并输出
代码如下:
- #include<cstdio>
- #include<cstring>
- #include<vector>
- using namespace std;
- const int maxn=10005;
- vector<int> son[maxn];
- int n;
- int p[maxn],in[maxn],dep[maxn];
- //dfs 获取结点深度
- void dfs(int root,int depth){
- dep[root]=depth;
- for(int i=0;i<son[root].size();i++){
- p[son[root][i]]=root;
- dfs(son[root][i],depth+1);
- }
- return;
- }
- //LCA 普通做法核心步骤
- int LCA(int u,int v){
- while(dep[u]>dep[v]) u=p[u];
- while(dep[v]>dep[u]) v=p[v];
- while(u!=v){
- u=p[u];
- v=p[v];
- }
- return u;
- }
- int main(){
- int T,a,b,u,v;//T 个测试样例
- scanf("%d",&T);
- while(T--){
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- son[i].clear();
- memset(in,0,sizeof(in));
- for(int i=1;i<n;i++){
- scanf("%d%d",&a,&b);
- son[a].push_back(b);
- // 代表 b 是父结点的个数
- in[b]++;
- }
- memset(dep,0,sizeof(dep));
- int root=0;
- for(int i=1;i<=n;i++)
- if(in[i]==0) root=i;
- p[root]=0;
- dfs(root,0);
- scanf("%d%d",&u,&v);
- printf("%d\n",LCA(u,v));
- }
- return 0;
- }
- /*
- 1
- 16
- 1 14
- 8 5
- 10 16
- 5 9
- 4 6
- 8 4
- 4 10
- 1 13
- 6 15
- 10 11
- 6 7
- 10 2
- 16 3
- 8 1
- 16 12
- 16 7
- */
倍增
思路:
让两个结点到达同一个深度, 再一起往上走, 但是这里的往上走不是一步步往上走, 而是先看最大深度, 在一步步地往回看.
例: a,b 两个结点到达了同一个深度, 再走 5 步便可以到达同一个结点 (即最近公共祖先), 我们便要凑 5. 我们先让他走到最大深度, 假如说最大深度为 32(2^5), 到达了同一个结点, 但是不是他们的最近公共祖先, 所以不走. 然后分别走 16(2^4),8(2^3) 都到达了同一个结点, 但不是最近公共祖先, 所以不走. 再走 4(2^2), 未到达同一结点, 走. 在看 2(2^1),2+4>5, 所以又到达了同一个结点, 还是不走. 最后 1(2^0),5=4+1, 走一步便是最近公共祖先.(大家可以用手模拟一下这个过程)
5 的二进制是 101, 就相当于 2^2+2^0, 也就是我们刚刚模拟的过程, 所以倍增也是基于二进制的思想.
基本步骤:
1, 用邻接表存图(这里用到的是用 vector)
2,dfs 获取各个结点的深度以及各个结点的第 2^i 个祖先结点的编号
3, 从最大深度开始一步步变小遍历, 如果到达了同一个点, 则不走; 如果没有到达同一个点, 则走
4, 返回最终结点的父节点即可
代码如下:
- #include<cstdio>
- #include<cstring>
- #include<vector>
- using namespace std;
- const int maxn=10005;
- vector<int> son[maxn];
- int n;
- int in[maxn],dep[maxn];
- int p[maxn][20];
- //dfs 获取结点深度, 更新祖先结点的信息
- void dfs(int prev,int root,int depth){
- dep[root]=depth;
- p[root][0]=prev;
- for(int i=1;i<20;i++)
- p[root][i]=p[p[root][i-1]][i-1];
- for(int i=0;i<son[root].size();i++)
- dfs(root,son[root][i],depth+1);
- return;
- }
- // 倍增算法核心步骤
- int LCA(int x,int y){
- if(dep[x]<dep[y]) swap(x,y);
- while(dep[x]>dep[y]) x=p[x][0];
- if(x==y) return x;
- for(int i=19;i>=0;i--)
- if(p[x][i]!=p[y][i]){
- x=p[x][i];
- y=p[y][i];
- }
- return p[x][0];
- }
- int main(){
- int T,a,b,u,v;
- scanf("%d",&T);
- while(T--){
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- son[i].clear();
- memset(in,0,sizeof(in));
- for(int i=1;i<n;i++){
- scanf("%d%d",&a,&b);
- son[a].push_back(b);
- in[b]++;
- }
- memset(dep,0,sizeof(dep));
- int root=0;
- for(int i=1;i<=n;i++)
- if(in[i]==0) root=i;
- dfs(0,root,0);
- scanf("%d%d",&u,&v);
- printf("%d\n",LCA(u,v));
- }
- return 0;
- }
- /*
- 1
- 16
- 1 14
- 8 5
- 10 16
- 5 9
- 4 6
- 8 4
- 4 10
- 1 13
- 6 15
- 10 11
- 6 7
- 10 2
- 16 3
- 8 1
- 16 12
- 16 7
- */
来源: http://www.bubuko.com/infodetail-3159817.html