\(LCA\) 之 \(Tarjan\)(离线)算法
什么是最近公共祖先?
在一棵没有环的树上,每个节点肯定有其父亲节点和祖先节点,而最近公共祖先,就是两个节点在这棵树上深度最大的公共的祖先节点。
换句话说,就是两个点在这棵树上距离最近的公共祖先节点。
所以\(LCA\)主要是用来处理当两个点仅有唯一一条确定的最短路径时的路径。
有人可能会问:那他本身或者其父亲节点是否可以作为祖先节点呢?
答案是肯定的,很简单,按照人的亲戚观念来说,你的父亲也是你的祖先,而\(LCA\)还可以将自己视为祖先节点。
举个例子吧,如下图所示\(4\)和\(5\)的最近公共祖先是\(2\),\(5\)和\(3\)的最近公共祖先是\(1\),\(2\)和\(1\)的最近公共祖先是\(1\)。
![](/i/i/?n=15&i=blog/818487/201510/818487-20151004150339121-181913844.png)
这就是最近公共祖先的基本概念了,那么我们该如何去求这个最近公共祖先呢?
通常初学者都会想到最简单粗暴的一个办法:对于每个询问,遍历所有的点,时间复杂度为\(O(n*q)\),很明显,\(n\)和\(q\)一般不会很小。
\(LCA\)常见的四种求法
算法 | 倍增 | \(Tarjan\) | \(DFS+ST\) | 线段树 |
---|---|---|---|---|
在线离线 | 在线算法 | 离线算法 | 在线算法 | 在线算法 |
时间复杂度 | \(O(logn) \sim O(nlogn)\) | \(O(n+q)\) | \(O(logn) \sim O(nlogn)\) | \(O(n) \sim O(nlogn)\) |
优缺点 | 简单, |
\(Tarjan\) 算法复杂度最低,代码也很简单,不易出错,可以一次性处理多条查询请求! | 简单粗暴 |
这篇博客主要是要介绍一下\(Tarjan\)算法
什么是\(Tarjan\)(离线)算法呢?顾名思义,就是在一次遍历中把所有询问一次性解决,所以其时间复杂度是\(O(n+q)\)。
\(Tarjan\)算法的优点在于 相对稳定,时间 复杂度也比较居中,也很 容易理解。
下面详细介绍一下\(Tarjan\)算法的基本思路:
- 任选一个点为根节点,从根节点开始
- 遍历该点\(u\)所有子节点\(v\),并标记这些子节点\(v\)已被访问过
- 若是\(v\)还有子节点,返回\(2\),否则下一步
- 合并\(v\)到\(u\)上
- 寻找与当前点\(u\)有询问关系的点\(v\)
- 若是\(v\)已经被访问过了,则可以确认\(u\)和\(v\)的最近公共祖先为\(v\)被合并到的父亲节点\(find(v)\)
遍历的话需要用到\(dfs\)来遍历(我相信来看的人都懂吧...),至于合并,最优化的方式就是利用 并查集 来合并两个节点。
下面上伪代码:
//merge和find为并查集合并函数和查找函数
tarjan(u){
st[u] = true;
for each(u,v){ //访问所有u子节点v
tarjan(v); //继续往下遍历
p[v] = find(u);//合并v到u上
}
for each(u,v){ //访问所有和u有询问关系的v
如果v被访问过;
u,v的最近公共祖先为find(v);
}
}
个人感觉这样还是有很多人不太理解,所以我打算模拟一遍给大家看。
建议拿着纸和笔跟着我的描述一起模拟!!
假设我们有一组数据 \(9\)个节点 \(8\)条边 联通情况如下:
\(1-2,1-3,2-4,2-5,3-6,5-7,5-8,7-9\) 即下图所示的树
设我们要查找最近公共祖先的点为\(9-8,4-6,7-5,5-3\)
设\(f[]\)数组为并查集的父亲节点数组,初始化\(f[i]=i,vis[]\)数组为是否访问过的数组,初始为\(0\);
![](/i/i/?n=15&i=blog/818487/201510/818487-20151005085438253-584479271.jpg)
下面开始模拟过程:
取\(1\)为 根节点,往下搜索 发现有两个儿子\(2\)和\(3\);
先搜\(2\),发现\(2\)有两个儿子\(4\)和\(5\),先搜索\(4\),发现\(4\)没有子节点,则寻找与其有关系的点;
发现\(6\)与\(4\)有关系,但是\(vis[6]=0\),即\(6\)还没被搜过,所以 不操作;
发现没有和\(4\)有询问关系的点了,返回此前一次搜索,更新\(vis[4]=1\);
![](/i/i/?n=15&i=blog/818487/201510/818487-20151005091215206-185829617.jpg)
表示\(4\)已经被搜完,更新\(f[4]=2\),继续搜\(5\),发现\(5\)有两个儿子\(7\)和\(8\);
先搜\(7\),发现\(7\)有一个子节点\(9\),搜索\(9\),发现没有子节点,寻找与其有关系的点;
发现\(8\)和\(9\)有关系,但是\(vis[8]=0\),即\(8\)没被搜到过,所以不操作;
发现没有和\(9\)有询问关系的点了,返回此前一次搜索,更新\(vis[9]=1\);
表示\(9\)已经被搜完,更新\(f[9]=7\),发现\(7\)没有没被搜过的子节点了,寻找与其有关系的点;
发现\(5\)和\(7\)有关系,但是\(vis[5]=0\),所以 不操作;
发现没有和\(7\)有关系的点了,返回此前一次搜索,更新\(vis[7]=1\);
![](/i/i/?n=15&i=blog/818487/201510/818487-20151005092745612-1059188156.jpg)
表示\(7\)已经被搜完,更新\(f[7]=5\),继续搜\(8\),发现\(8\)没有子节点,则寻找与其有关系的点;
发现\(9\)与\(8\)有关系,此时\(vis[9]=1\),则他们的最近公共祖先为\(find(9)=5\);
(find(9)
的顺序为f[9]=7-->f[7]=5-->f[5]=5 return 5;
)
发现没有与\(8\)有关系的点了,返回此前一次搜索,更新\(vis[8]=1\);
表示\(8\)已经被搜完,更新\(f[8]=5\),发现\(5\)没有没搜过的子节点了,寻找与其有关系的点;
![](/i/i/?n=15&i=blog/818487/201510/818487-20151005094054237-333460930.jpg)
发现\(7\)和\(5\)有关系,此时\(vis[7]=1\),所以他们的最近公共祖先为\(find(7)=5\);
(\(find(7)\)的顺序为f[7]=5-->f[5]=5 return 5;
)
又发现\(5\)和\(3\)有关系,但是\(vis[3]=0\),所以不操作,此时\(5\)的子节点全部搜完了;
返回此前一次搜索,更新\(vis[5]=1\),表示\(5\)已经被搜完,更新\(f[5]=2\);
发现\(2\)没有未被搜完的子节点,寻找与其有关系的点;
又发现没有和\(2\)有关系的点,则此前一次搜索,更新\(vis[2]=1\);
![](/i/i/?n=15&i=blog/818487/201510/818487-20151005100146690-1294857778.jpg)
表示\(2\)已经被搜完,更新\(f[2]=1\),继续搜\(3\),发现\(3\)有一个子节点\(6\);
搜索\(6\),发现\(6\)没有子节点,则寻找与\(6\)有关系的点,发现\(4\)和\(6\)有关系;
此时\(vis[4]=1\),所以它们的最近公共祖先为\(find(4)=1\);
(\(find(4)\)的顺序为f[4]=2-->f[2]=2-->f[1]=1 return 1;
)
发现没有与\(6\)有关系的点了,返回此前一次搜索,更新\(vis[6]=1\),表示\(6\)已经被搜完了;
![](/i/i/?n=15&i=blog/818487/201510/818487-20151005101758206-890675418.jpg)
更新\(f[6]=3\),发现\(3\)没有没被搜过的子节点了,则寻找与\(3\)有关系的点;
发现\(5\)和\(3\)有关系,此时\(vis[5]=1\),则它们的最近公共祖先为\(find(5)=1\);
(\(find(5)\)的顺序为f[5]=2-->f[2]=1-->f[1]=1 return 1;
)
发现没有和\(3\)有关系的点了,返回此前一次搜索,更新\(vis[3]=1\);
![](/i/i/?n=15&i=blog/818487/201510/818487-20151005102559159-375592206.jpg)
更新\(f[3]=1\),发现\(1\)没有被搜过的子节点也没有有关系的点,此时可以退出整个\(dfs\)了。
经过这次\(dfs\)我们得出了所有的答案,有没有觉得很神奇呢?是否对\(Tarjan\)算法有更深层次的理解了呢?
标准代码模板
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 500010, M = N << 1;
//链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
vector<PII> query[N]; // query[u]: first:询问的另一个顶点; second:询问的编号
int n, m, s;
int p[N]; // 并查集数组
bool st[N]; // tarjan算法求lca用到的是否完成访问的标识
int lca[N]; // 结果数组
int find(int x) {
if (p[x] != x) p[x] = find(p[x]); //路径压缩
return p[x];
}
void tarjan(int u) {
// ① 标识u已访问
st[u] = true;
//② 枚举u的临边,tarjan没有访问过的点
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!st[j]) {
tarjan(j);
//③ 完成访问后,j点加入u家族
p[j] = u;
}
}
//④ 每个已完成访问的点,记录结果
for (auto q : query[u]) {
int v = q.first, id = q.second;
if (st[v]) lca[id] = find(v);
}
}
int main() {
memset(h, -1, sizeof h);
scanf("%d %d %d", &n, &m, &s);
int a, b;
for (int i = 1; i < n; i++) {
scanf("%d %d", &a, &b);
add(a, b), add(b, a);
}
for (int i = 1; i <= m; i++) {
scanf("%d %d", &a, &b);
query[a].push_back({b, i});
query[b].push_back({a, i});
}
//初始化并查集
for (int i = 1; i <= n; i++) p[i] = i;
tarjan(s);
//输出答案
for (int i = 1; i <= m; i++) printf("%d\n", lca[i]);
return 0;
}
标签:Tarjan,int,离线,find,vis,算法,祖先,LCA,节点
From: https://www.cnblogs.com/littlehb/p/16895390.html