【图论】TarjanLCA算法
2021-03-07 02:29
标签：加速 访问 code == 路径 tin str 倍增lca 数组 算法的原理：把dfs的点分为三类： vis[u]=0 表示这个点从未访问 Tarjan算法把lca(x,y)的查询丢给x和y的查询数组记录。后序遍历，总是会先遍历y再遍历x，那么vis[y]=2，要么x是y的祖先，要么是x的某个祖先是y的祖先。这里套个并查集加速一下，对于每个退栈的节点，把它（以及它的子树当然也是退栈了的）合并到其父亲上，那么在查询y在并查集中的代表元素中，会恰好查到还在栈中的那个最深的x的祖先，这个恰好就是lca了。 仔细一看觉得这个甚至比倍增LCA还要更好写一些？倍增LCA可以找x和y路径上的最小值，Tarjan怎么找。 【图论】TarjanLCA算法 标签：加速 访问 code == 路径 tin str 倍增lca 数组 原文地址：https://www.cnblogs.com/purinliang/p/14284957.html
vis[u]=1 表示这个点在栈中，是u点的祖先
vis[u]=2 表示这个点已经退栈const int MAXN = 200000 + 10;
const int MAXM = 2000000 + 10;
int n, m;
vi G[MAXN];
int vis[MAXN];
int fa[MAXN];
int ans[MAXN];
struct Query {
int x, y, id;
} query[MAXN];
void Init() {
for(int i = 1; i
上一篇：js 随机打乱数组
下一篇：C#中的异步和多线程