【C++】图论|最近公共祖先(LCA)模板

最近公共祖先(LCA)是图论中一类常见的问题。这里我们主要考虑的是两个节点的最近公共祖先。

题目:P3379 【模板】最近公共祖先(LCA)https://www.luogu.com.cn/problem/P3379

朴素法(直接dfs)

直接一层一层搜索祖先,即普通dfs。显然无法通过此题目,这里就不提供代码了。

倍增法

是朴素的改进,理解起来很简单。就是先把两个点提到树的同一高度,再一起往上跳,直到相遇。

但是代码实际上不是很好理解,研究了足足一天(也许笔者比较笨吧)

属于在线算法(即每次查询都现算),时间复杂度O(nlog n)

*这里为了降低常数,预处理了log2

// 倍增算法
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;
vector<vector<int>> fa, edg;
vector<int> depth, lg2;

void dfs(int now, int fath)
{
	fa[now][0] = fath;
	depth[now] = depth[fath] + 1;
	for (int i = 1; i <= lg2[depth[now]]; i++)
	{
		fa[now][i] = fa[fa[now][i - 1]][i - 1];
	}
	for (auto& i : edg[now])
	{
		if (i != fath) dfs(i, now);
	}
}

int lca(int x, int y)
{
	if (depth[x] < depth[y]) swap(x, y);
	while (depth[x] > depth[y])
	{
		x = fa[x][lg2[depth[x] - depth[y]] - 1];
	}
	if (x == y) return x;
	for (int k = lg2[depth[x]] - 1; k >= 0; k--)
	{
		if (fa[x][k] != fa[y][k])
		{
			x = fa[x][k];
			y = fa[y][k];
		}
	}
	return fa[x][0];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m, s, x, y;
	cin >> n >> m >> s;
	fa.resize(n + 1);
	edg.resize(n + 1);
	depth.resize(n + 1);
	lg2.resize(n + 1);
	// 预处理log2
	for (int i = 1; i <= n; i++)
	{
		lg2[i] = lg2[i - 1] + (1 << lg2[i - 1] == i);
	}
	for (auto& i : fa) i.resize(lg2[n] + 1);
	for (int i = 1; i < n; i++)
	{
		cin >> x >> y;
		edg[x].emplace_back(y);
		edg[y].emplace_back(x);
	}
	dfs(s, 0);
	while (m--)
	{
		cin >> x >> y;
		cout << lca(x, y) << endl;
	}
	return 0;
}

LCA Tarjan

前置知识:并查集

注意:不要和连通性的SCC Tarjan搞混,我的一位同学就做出过只因看见算法名字一样便用LCA Trajan处理缩点的逆天操作,还抱怨咋改也不过😅

LCA Tarjan是一种离线算法,即预处理所有查询。

一点小知识:并查集,LCA Tarjan,以及强连通下的缩点SCC Tarjan,双连通下割点/桥SCC Tarjan,斐波那契堆等(算)法如其名,均为美国计算机科学家,图灵奖得主罗伯特·塔扬(Robert Endre Tarjan)所发明。哎wc罗伯特怎么这么郝啊.jpg

非常巧妙的利用了并查集压缩路径的过程,在压缩的同时利用dfs完成查找,总之非常非常巧妙。

时间复杂度接近O(n).

// Tarjan
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;
vector<vector<pair<int, int>>> query;
vector<vector<int>> edg;
vector<int> fa, ans, vis;

void init(int n)
{
	fa.resize(n + 3);
	for (int i = 1; i <= n; i++)
	{
		fa[i] = i;
	}
}

int find(int x)
{
	if (x != fa[x])
	{
		fa[x] = find(fa[x]);
	}
	return fa[x];
}

void tarjan(int x)
{
	vis[x] = 1;
	for (auto& i : edg[x])
	{
		if (!vis[i])
		{
			tarjan(i);
			fa[i] = x;
		}
	}
	for (auto& i : query[x])
	{
		if (vis[i.first])
		{
			ans[i.second] = find(i.first);
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m, s, x, y;
	cin >> n >> m >> s;
	init(n);
	edg.resize(n + 3);
	ans.resize(n + 3);
	vis.resize(n + 3, 0);
	query.resize(n + 3);
	for (int i = 1; i < n; i++)
	{
		cin >> x >> y;
		edg[x].emplace_back(y);
		edg[y].emplace_back(x);
	}
	for (int i = 1; i <= m; i++)
	{
		cin >> x >> y;
		query[x].emplace_back(make_pair(y, i));
		query[y].emplace_back(make_pair(x, i));
	}
	tarjan(s);
	for (int i = 1; i <= m; i++)
	{
		cout << ans[i] << endl;
	}
	return 0;
}

目前有关LCA就这些内容。希望我以后遗忘可以慢一点。。。同时如果这也能帮到你,我很荣幸。真的。。

版权声明:
作者:Toms Project
链接:https://blog.projectoms.com/pages/1510.html
来源:Toms Project 官方博客
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
打赏
< <上一篇
下一篇>>
文章目录
关闭
目 录