最近公共祖先

学习
字数统计: 2.4k   |   阅读时长≈ 10 分钟

LCA-最近公共祖先

0. 概述

  • 两个节点的最近公共祖先 $(Lowest Common Ancestor,LCA)$ 就是这两个点的公共祖先里面，离他们最近的那个

1. 倍增算法

1.1. 数据结构

  • $dep[u]$：存储节点$u$的深度
  • $fa[u][i]$：存储从节点$u$向上跳$2^i$层的祖先节点，$i=0,1,2,3···$，例如，节点$9$向上跳$2^0$层的祖先是3，跳$2^1$层祖先是6，跳$2^2$层祖先是1，跳$2^3$层祖先是0（哨兵）

image-20240214111156105

1
2
3
4
5
const int N=5e5+10; // 节点总数
int n,m,s,a,b;
vector<int> e[N]; // 对所有节点开一个邻接表
int dep[N],fa[N][20]; // dep[i]:节点i的深度,fa[i][20]:存储每个节点的祖先
// 注意,因为2^20大概等于1e6左右,是大于MAXN的,所以层数最大开20即可

1.2. 算法过程

总时间复杂度$O((n+m)log^n)$，$n,m$分别是节点总数和查询次数

  • $dfs$一遍，创建$ST$表，倍增递推，$fa[u][i]=fa[fa[u][i-1]][i-1]$，即从节点$u$跳到$2^i$层，分两步跳，每步跳$2^{i-1}$层，第一步跳到$fa[u][i-1]$，那么第二步跳到$fa[fa[u][i-1]][i-1]$

image-20240214111903418

1
2
3
4
5
6
7
8
9
10
11
12
// dfs建st表
void dfs(int u,int father) {
	dep[u]=dep[father]+1;
	// 向上跳1,2,4,...步的祖先节点
	fa[u][0]=father; // 向上跳一步得到父节点
	for(int i=1;i<=19;i++) 
		fa[u][i]=fa[fa[u][i-1]][i-1]; // 向上跳最大深度
	// 对儿子节点继续dfs建表
	for(int v:e[u]) 
		// 判断是不是父节点,避免往上走
		if(v!=father) dfs(v,u);
}
  • 利用ST表建LCA
    • (1) 第一阶段，将u,v跳到同一层，设u,v两点的深度之差为y，将y进行二进制拆分，可以将y次游标跳跃优化为”y的二进制表示所含1的个数“次游标跳跃，一定能跳到同一层。例如，y=1019(0..01111111011)=512+256+…+8+2+1，不越界则跳，共跳9次到达。
    • (2) 第二阶段，将u,v一起跳到LCA的下一层从最大的ⅰ开始循环尝试，一直尝试到0，最后游标u,v一定能停在LCA的下一层。例如，y=1019(0..01111111011)两游标会跳512+256+…+8+2=1018层，共跳8次到达LCA的下一层。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 根据st找LCA
int lca(int u,int v) {
	// 保证u的深度>=v的深度,便于代码书写统一
	if(dep[u]<dep[v]) swap(u,v); 
	// 先让u,v跳到同一层去
	for(int i=19;i>=0;i--)
		if(dep[fa[u][i]]>=dep[v])
			u=fa[u][i];
	if(u==v) return v; // 如果uv同层后发现u==v,说明v就是u的祖先,那么返回v
	// 再跳到LCA的下一层
	for(int i=19;i>=0;i--) 
		// uv同层后一起往上跳2^i层,如果结果不同则uv递归到父节点
		if(fa[u][i]!=fa[v][i])
			u=fa[u][i],v=fa[v][i];
	return fa[u][0]; // 跳到LCA的下一层后,那么再往上跳一步就得到公共祖先
}

1.3. 完整代码

image-20240214122324096 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

// 题目描述: 

const int N=5e5+10; // 节点总数
int n,m,s,a,b;
vector<int> e[N]; // 对所有节点开一个邻接表
int dep[N],fa[N][20]; // dep[i]:节点i的深度,fa[i][20]:存储每个节点的祖先
// 注意,因为2^20大概等于1e6左右,是大于MAXN的,所以层数最大开20即可

// dfs建st表
void dfs(int u,int father) {
	dep[u]=dep[father]+1;
	// 向上跳1,2,4,...步的祖先节点
	fa[u][0]=father; // 向上跳一步得到父节点
	for(int i=1;i<=19;i++) 
		fa[u][i]=fa[fa[u][i-1]][i-1]; // 向上跳最大深度
	// 对儿子节点继续dfs建表
	for(int v:e[u]) 
		// 判断是不是父节点,避免往上走
		if(v!=father) dfs(v,u);
}

// 根据st找LCA
int lca(int u,int v) {
	// 保证u的深度>=v的深度,便于代码书写统一
	if(dep[u]<dep[v]) swap(u,v); 
	// 先让u,v跳到同一层去
	for(int i=19;i>=0;i--)
		if(dep[fa[u][i]]>=dep[v])
			u=fa[u][i];
	if(u==v) return v; // 如果uv同层后发现u==v,说明v就是u的祖先,那么返回v
	// 再跳到LCA的下一层
	for(int i=19;i>=0;i--) 
		// uv同层后一起往上跳2^i层,如果结果不同则uv递归到父节点
		if(fa[u][i]!=fa[v][i])
			u=fa[u][i],v=fa[v][i];
	return fa[u][0]; // 跳到LCA的下一层后,那么再往上跳一步就得到公共祖先
}

int main() {
	// n:节点数,m:询问个数,s:根节点的序号
	cin>>n>>m>>s;
	// a,b节点之间有一条边(数据保证构成树)
	// 节点数为n,树有n-1条边
	for(int i=1;i<n;i++) {
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs(s,0);
	// m次查询
	while(m--) {
		scanf("%d%d",&a,&b);
		printf("%d\n",lca(a,b));
	}
	return 0;
}

2. Tarjan算法

  • Tarjan(塔扬)算法是一种离线算法，巧妙利用并查集维护祖先节点。
  • 离线算法：一开始需要知道问题的所有输入数据，才能计算出结果。

2.1. 数据结构

image-20240214145136351 
1
2
3
4
5
6
7
8
9
10
const int N=5e5+5;
const int M=1e5+5;

vector<int> e[N]; // e[u]存树边,e[1]=5,e[5]=1
// N次查询,存两次,query[3]={4,1},query[4]={3,1},表示第一次查询,查的是{3,4}的LCA
vector<PII> query[N]; 
// fa[u]:存父节点,fa[5]=1,节点5的父节点是1
// vis[u]:打标记
// ans[i]:存储每次查询的结果
int fa[N],vis[N],ans[M];

2.2. 算法过程

总时间复杂度$O(m+n)$，其中n是节点个数，m是查询总次数

  1. 从根开始深搜遍历，入u时打标记
  2. 枚举u的儿子v，遍历完v的子树，回u时把v指向u
  3. 遍历完u的儿子们，离u时枚举以u为起点的查询，若终点V被搜过则查找v的根，即u,v的LCA，答案记入ans[]
  4. 递归遍历完整颗树，得到全部查询答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 并查集
int find(int u) {
	if(u==fa[u]) return u;
	return fa[u]=find(fa[u]);
}

// 塔扬算法
void tarjan(int u) {
	// 1:入
	vis[u]=true; // 入u时标记
	// 枚举u的所有儿子
	for(auto v:e[u]) {
		// 2:下,判重,保证一定往下走,防止往回搜
		if(!vis[v]) {
			tarjan(v);
			fa[v]=u; // 3:回,回u时,v指向u,让儿子指向父亲,维护并查集
		}
	}
	// 4:离,遍历完u的儿子之后,离u时遍历以u为起点的查询
	for(auto q:query[u]) {
		// v:取出终点,i:第几次查询
		int v=q.x,i=q.y;
		// 如果终点被搜过,则查找v的根,即u/v的LCA,答案计入ANS
		if(vis[v]) ans[i]=find(v); 
	}
}

2.3. 完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

// 题目描述: 

const int N=5e5+5,M=2*N; // 查询的边要建两次

vector<int> e[N]; // e[u]存树边,e[1]=5,e[5]=1
// N次查询,存两次,query[3]={4,1},query[4]={3,1},表示第一次查询,查的是{3,4}的LCA
vector<PII> query[N]; 
// fa[u]:存父节点,fa[5]=1,节点5的父节点是1
// vis[u]:打标记
// ans[i]:存储每次查询的结果
int fa[N],vis[N],ans[M];

int n,m,s,a,b;

// 并查集
int find(int u) {
	if(u==fa[u]) return u;
	return fa[u]=find(fa[u]);
}

// 塔扬算法
void tarjan(int u) {
	// 1:入
	vis[u]=true; // 入u时标记
	// 枚举u的所有儿子
	for(auto v:e[u]) {
		// 2:下,判重,保证一定往下走,防止往回搜
		if(!vis[v]) {
			tarjan(v);
			fa[v]=u; // 3:回,回u时,v指向u,让儿子指向父亲,维护并查集
		}
	}
	// 4:离,遍历完u的儿子之后,离u时遍历以u为起点的查询
	for(auto q:query[u]) {
		// v:取出终点,i:第几次查询
		int v=q.x,i=q.y;
		// 如果终点被搜过,则查找v的根,即u/v的LCA,答案计入ANS
		if(vis[v]) ans[i]=find(v); 
	}
}


int main() {
	cin>>n>>m>>s; // n:节点数,m:查询数,s:根节点
	for(int i=1;i<n;i++) {
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	for(int i=1;i<=m;i++) {
		scanf("%d%d",&a,&b);
		// 查询建边两次,因为不知道在tarjan算法中查询用哪个点
		query[a].push_back({b,i});
		query[b].push_back({a,i});
	}
	for(int i=1;i<=N;i++) fa[i]=i; // 并查集初始化
	tarjan(s);
	for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
	return 0;
}

3. 算法对比

image-20240214150921613
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信