当前位置:   article > 正文

【算法】最近公共祖先(lca)——倍增,tarjan_最近公共祖先 图 倍增

最近公共祖先 图 倍增

问题引入

给定一棵包含 n 个节点的有根无向树,节点编号互不相同,
有 m 个询问,每个询问给出了一对节点的编号 x 和 y,询问 x 与 y 的祖孙关系。
并查集吗?可以,但时间复杂度太高了,很容易TLE,所以我们用LCA。

介绍

最近公共祖先是什么意思呢?其实就是对于两个点x和y,如果点t满足既是x的祖先又是y的祖先,同时是离它们最近共同的祖先,那么t就是x,y的最近公共祖先。
如图:
在这里插入图片描述

a是b,c的最近公共祖先,a是p,q的最近公共祖先。

lca就是用来求两点的最近公共祖先的算法。

倍增(在线算法)

原理

类似二分,用二进制数求出两点间的lca
分两种情况:
1.两点在同一棵子树上:
如一个链表 a-b-c,其中a为根节点,求lca(a,c)
很容易得出lca(a,c)=a

2.两点不在同一棵子树上:
首先,将两点弄到同一个高度。
接着,两点同时往上跳同一高度,跳到极限(再往上一格就撞在一起)
最后,极限+1就是lca了
如图:在这里插入图片描述
求lca(g,f)
先弄到同一高度(蓝色箭头)
然后一起跳(红色箭头)
最后跳到极限,所以lca(g,f)=a

代码实现

存边

我们用邻接表存边:

struct Edge
{
	int next,t;	
}edge[N];
inline void add(int x,int y)
{
	edge[++cnt].t=y,edge[cnt].next=head[x],head[x]=cnt;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

需要前置知识:邻接表

初始化

想要实现这个算法,首先我们要记录各个点的深度和它跳2^i步后的节点
我们用数组d表示每个节点的深度,f[i][j]表示节点i 跳2^j步后的节点位置
所以初始化如下:

void dfs(int u,int fa)//u表示当前节点,fa表示它的父亲节点
{
	f[u][0]=fa,d[u]=d[fa]+1;
	for(int i=1;i<=lg[d[u]];i++)//非常关键
		f[u][i]=f[f[u][i-1]][i-1];//意思是u的2^i祖先等于u的2^(i-1)祖先的2^(i-1)祖先
								  //因为2^i = 2^(i-1) + 2^(i-1)
	for(int i=head[u];i;i=edge[i].next)//便利u的所有相连节点
		if(edge[i].t!=fa)//如果不是父亲节点
			dfs(edge[i].t,u);//继续搜索
}
for(int i=1;i<=n;i++)//预先算出log_2(i)+1的值,用的时候直接调用就可以了
	lg[i]=lg[i-1]+(1<<lg[i-1]==i);//看不懂的可以手推一下
dfs(s,0);//s为根节点
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

LCA

I.深度调换

我们求lca(x,y),默认x比y要深,所以如果x没y深,将x,y交换一下:

if(d[x]<d[y])
	swap(x,y);//注意 交换x和y,不是d[x]和d[y]
  • 1
  • 2
II.调至同一深度

我们已经让x的深度比y大了,现在将它们调至同一深度:

while(d[x]>d[y])
	x=f[x][lg[d[x]-d[y]]-1];//手动推一下,每次都跳到准极限
  • 1
  • 2
III.特殊情况

现在x和y在同一深度,如果x==y,那么x就是lca(x,y)的值:

if(x==y)
	return x;
  • 1
  • 2
IV.一起跳

现x和y在同一深度的不同子树上,我们让它们一起跳2^i步,直到极限(上文说过):

for(int i=lg[d[x]]-1;i>=0;i--)
	if(f[x][i]!=f[y][i])//如果跳了之后不相等,就跳
		x=f[x][i],y=f[y][i];
  • 1
  • 2
  • 3
V.返回

此时x和y都跳到了极限,所以极限+1为所求:

return f[x][0];
  • 1
VI.例子
int lca(int x,int y)
{
	if(d[x]<d[y])
		swap(x,y);
	while(d[x]>d[y])
		x=f[x][lg[d[x]-d[y]]-1];
	if(x==y)
		return x;
	for(int i=lg[d[x]]-1;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

例题

题目

祖孙询问
给定一棵包含 n 个节点的有根无向树,节点编号互不相同,
有 m 个询问,每个询问给出了一对节点的编号 x 和 y,询问 x 与 y 的祖孙关系。

输入格式
输入第一行包括一个整数 表示节点个数;
接下来 n 行每行一对整数 a 和 b,表示 a 和 b 之间有一条无向边。如果 b 是 −1,那么 a 就是树的根;
第 n+2 行是一个整数 m 表示询问个数;
接下来 m 行,每行两个不同的正整数 x 和 y,表示一个询问。
1≤n,m≤4×104,
1≤每个节点的编号≤4×104

输出格式
对于每一个询问,若 x 是 y 的祖先则输出 1,若 y 是 x 的祖先则输出 2,否则输出 0。

输入/输出例子1
输入:

10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19

输出:

1
0
0
0
2
样例解释

code

#include<bits/stdc++.h>
using namespace std;
struct fy
{
	int t,next;
}edge[1000001];
int head[1000001],cnt,x,y,n,m,s,d[1000001],f[1000001][22],lg[1000001];
void add(int x,int y)
{
	edge[++cnt].t=y,edge[cnt].next=head[x],head[x]=cnt;
}
void dfs(int u,int fa)
{
	f[u][0]=fa,d[u]=d[fa]+1;
	for(int i=1;i<=lg[d[u]];i++)
		f[u][i]=f[f[u][i-1]][i-1];
	for(int i=head[u];i;i=edge[i].next)
		if(edge[i].t!=fa)
			dfs(edge[i].t,u);
}
int lca(int x,int y)
{
	if(d[x]<d[y])
		swap(x,y);
	while(d[x]>d[y])
		x=f[x][lg[d[x]-d[y]]-1];
	if(x==y)
		return x;
	for(int i=lg[d[x]]-1;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		if(y!=-1)
			add(x,y),add(y,x);
		else
			s=x;
	}
	scanf("%d",&m);
	for(int i=1;i<=n;i++)
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	dfs(s,0);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		int z=lca(x,y);
		if(z==x)
			printf("1\n");
		else if(z==y)
			printf("2\n");
		else
			printf("0\n");
	}
	return 0;
}
  • 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

总结

类似二分,O(nlogn)

Tarjan(离线算法)

原理

类似dfs,先搜一块子树,根据已知条件求答案
区别倍增:先搜集完答案信息再dfs,不是拿一个问题得出一个答案
方法:并查集

代码实现

初始化

存边
struct fy
{
	int next,t;	
}edge[N];
void add(int x,int y)
{
	edge[++cnt].t=y,edge[cnt].next=head[x],head[x]=cnt;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
并查集
int ga(int x)
{
	if(x!=fa[x])
		fa[x]=ga(fa[x]);
	return fa[x];
}
for(int i=1;i<=n;i++)
	fa[i]=i;//并查集初始化
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

Tarjan

I.标记+枚举子节点
	vis[u]=1;//标记已经搜过
	for(int i=head[u];i;i=edge[i].next)//枚举全部子节点
	{
		int j=edge[i].t;
		if(!vis[j])//判断标记
			tarjan(j),fa[j]=u;
	}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
II.查找答案
	for(int i=0;i<a[u].size();i++)//查找问了关于u的问题
	{
		int y=a[u][i].u,id=a[u][i].v;
		if(vis[u])//如果找过了
			b[id]=ga(y);//直接得答案
	}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

例题

题目

最近公共祖先
如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先

输入格式
第一行包含三个正整数 N,M,S, 分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N-1 行每行包含两个正整数 x, y ,表示 x 结点和 y 结点之间有一条直接连接的边(数据保证可以构成树)。
接下来 M 行每行包含两个正整数 a, b ,表示询问 a 结点和 b 结点的最近公共祖先。 1<=N,M<=500000

输出格式
输出包含 M 行,每行包含一个正整数,依次为每一个询问的结果。

输入/输出例子1
输入:

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

输出:

4
4
1
4
4

样例解释

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
struct fy
{
	int next,t;	
}edge[N];
struct ff
{
	int u,v;
};
int head[N],cnt,fa[N],n,m,s,b[N],vis[N],x,y;
vector<ff>a[N];
void add(int x,int y)
{
	edge[++cnt].t=y,edge[cnt].next=head[x],head[x]=cnt;
}
int ga(int x)
{
	if(x!=fa[x])
		fa[x]=ga(fa[x]);
	return fa[x];
}
void tarjan(int u)
{
	vis[u]=1;
	for(int i=head[u];i;i=edge[i].next)
	{
		int j=edge[i].t;
		if(!vis[j])
			tarjan(j),fa[j]=u;
	}
	for(int i=0;i<a[u].size();i++)
	{
		int y=a[u][i].u,id=a[u][i].v;
		if(vis[u])b[id]=ga(y);
	}
}
signed main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<n;i++)
		scanf("%d%d",&x,&y),add(x,y),add(y,x);
	for(int i=1;i<=m;i++)
		scanf("%d%d",&x,&y),a[x].push_back({y,i}),a[y].push_back({x,i});
	for(int i=1;i<=n;i++)
		fa[i]=i;
	tarjan(s);
	for(int i=1;i<=m;i++)
		printf("%d\n",b[i]);
} 
  • 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

总结

类dfs,常数优化,不过尽量打倍增

总结

很好的一个树形结构的算法,蒟蒻可以去这里刷题:lca刷题处

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/455174
推荐阅读
相关标签
  

闽ICP备14008679号