【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就这些内容。希望我以后遗忘可以慢一点。。。同时如果这也能帮到你，我很荣幸。真的。。