Tarjan 算法是一种 离线算法,需要使用并查集记录某个结点的祖先结点。
并没有传说中的那么快。
过程
将询问都记录下来,将它们建成正向边和反向边。
在 dfs 的过程中,给走过的节点打上标记,同时维护并查集,这里利用了回溯的思想,如果 \(u\) 节点的这棵子树没搜完,那么 fa[u] = u;
,搜完后,在更新并查集。
我们假设查询 \(u\) 和 \(v\) 的最近公共祖先,搜到节点 \(u\),如果另一个节点 \(v\) 已经被搜到过了,那么 \(v\) 点的并查集祖先就是 \(u\) 和 \(v\) 的最近公共祖先。
如果第一次查询 \(v\) 点时,发现 \(v\) 点已经被搜到了,说明 \(u\) 和 \(v\) 点在同一棵子树中,并且这个子树是所有包括了 \(u\) 点和 \(v\) 点的子树中
siz
最小的,这棵子树的根也是在所有符合条件的子树的根中离 \(u\) 和 \(v\) 最近的,即这棵子树的根就是 \(u\) 和 \(v\) 的最近公共祖先,而 \(v\) 的并查集祖先就是这个根节点。
代码
结构体记录询问
int cnt = 1;
struct query {
int v, lca, nxt;
} q[N << 1];
记录询问、初始化
for (int i = 1, x, y; i <= m; ++ i) {
scanf("%d%d", &x, &y);
add_query(x, y);
add_query(y, x);
}
for (int i = 1; i <= n; ++ i) {
fa[i] = i;
}
tarjan、并查集文章来源:https://www.toymoban.com/news/detail-429730.html
void tarjan(int u) {
fa[u] = u;
vis[u] = 1;
for (int v : son[u]) {
if (!vis[v]) {
tarjan(v);
fa[v] = u;
}
}
int v;
for (int i = h[u]; i; i = q[i].nxt) {
if (vis[v = q[i].v]) {
q[i].lca = q[i ^ 1].lca = find(v);
}
}
}
fa[u] = u;
是为了保证在 \(u\) 这棵子树没有搜完的情况下,让它子树里的节点的并查集找祖先时找到的是它。文章来源地址https://www.toymoban.com/news/detail-429730.html
到了这里,关于「学习笔记」tarjan 求最近公共祖先的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!