利用倍增的思想实现LCA算法
目录
前言
LCA
算法指的是最近公共祖先(Lowest Common Ancestor
),这里的最近指的是给定的两个点中所有的公共祖先中,距离根节点最远的节点,而且这两点到最近公共祖先的距离只和也是这两点之间的最短路径。
实现
实现该算法一般是借助每个节点的深度信息进行求解,具体为:
假设要求x
和y
的LCA
,不妨假设depth[x] > depth[y]
,我们先让x
往上跳(朝着根的方向),直到二者的深度相同,然后x
和y
同时网上跳,最终二者一定会在某一点相遇,这点就是所求。
这也叫朴素实现方法,当一棵树深度很大,查询点都是比较深的时候,此时在网上跳的过程会花费大量的时间,时间复杂度是O(n)
。
而倍增思想解决的是,优化向上跳转的过程,每次尽可能地往上跳更多的距离。
相关代码说明请看代码注释:
/*
* @Author : YaleXin
* @Email : me@yalexin.top
* @LastEditors : YaleXin
*/
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
// const int MAX_N = 5e5 + 1, MAX_M = 5e5 + 1;
const int MAX_N = 5e2 + 1, MAX_M = 5e2 + 1;
struct Edge{
int v, next;
}edges[MAX_M << 1];
// head[] 节点i的第一条边,depth[] 节点的深度, f[][] 第i号节点的第2^j个祖先
int head[MAX_N], edgeNum = 1, depth[MAX_N], f[MAX_N][22], n;
// 预处理 log2(i) 向下取整的值
int lg2[MAX_N];
void preLg2(){
lg2[2] = 1;
for(int i = 3; i <= n; ++i)
lg2[i] = lg2[i - 1] + (2 << lg2[i - 1] == i);
}
// 采用链式前向星方式模拟链表
inline void add(int u, int v){
edges[edgeNum].v = v, edges[edgeNum].next = head[u];
head[u] = edgeNum++;
}
// 快速读入,可理解为 scanf()
inline int read(){
int sum = 0;
char ch = getchar();
while (ch < '0' || ch > '9')ch = getchar();
while (ch <= '9' && ch >= '0'){
sum = (sum << 1) + (sum << 3) + ch - '0';
ch = getchar();
}
return sum;
}
void dfs(int nowId, int fa){
// 第 2 ^ 0 即第一个祖先(从 nowId 往根节点方向)
f[nowId][0] = fa;
depth[nowId] = depth[fa] + 1;
for (int i = 1; i <= lg2[depth[nowId]]; i++)
// nowId 的第 2 ^ i 祖先是它的第 2 ^ (i - 1)个祖先的第 2 ^ (i - 1)个祖先
// 要画图才能理解
f[nowId][i] = f[f[nowId][i - 1]][i - 1];
for (int eId = head[nowId]; eId; eId = edges[eId].next)
if (edges[eId].v != fa)dfs(edges[eId].v, nowId);
}
int lca(int x, int y){
if (depth[x] < depth[y])swap(x, y);
// 目的是将二者处理到同一个高度
while (depth[x] > depth[y])
// 以高度差为依据进行跳
x = f[x][lg2[depth[x] - depth[y]]];
// 二者相等,毫无疑问,此时 x 就是 y 的祖先
if(x == y)return x;
for (int step = lg2[depth[x]];step >= 0; step--)
if (f[x][step] != f[y][step])
x = f[x][step], y = f[y][step];
return f[x][0];
}
int main(){
n = read();
int m = read(), s = read(), u, v;
for(int i = 1; i < n; i++){
u = read(), v = read();
add(u, v), add(v, u);
}
preLg2();
dfs(s, 0);
for (int i = 1; i <= m; i++){
u = read(), v = read();
printf("%d\n", lca(u, v));
}
return 0;
}
/*
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
*/
题目参考:洛谷P3397
本文由「黄阿信」创作,创作不易,请多支持。
如果您觉得本文写得不错,那就点一下「赞赏」请我喝杯咖啡~
商业转载请联系作者获得授权,非商业转载请附上原文出处及本链接。
关注公众号,获取最新动态!
历史评论
开始评论