浅谈 Tarjan 算法

本文在洛谷专栏中进行审核且通过，大家点个赞支持一下吧！
最近学了些新算法，过来做下笔记，以免以后忘了。
前置知识

Tarjan 算法的时间复杂度为 \(O(n + m)\)。
在除了求最近公共祖先的 Tarjan 算法里，都会用到两个数组和一个概念，在这里写清楚一点，以免后面讲得云里雾里。
对图深搜时，每一个节点只访问一次，被访问过的节点与边构成搜索树。

• 时间戳 \(\textup{dfn}_x​\)：表示节点 \(x​\) 第一次被访问的顺序。
  
• 追溯值 \(\textup{low}_x​\)：从节点 \(x​\) 出发，最早能访问到的最早时间戳。
  

当然，这两个数组的含义在不同的 Tarjan 算法中都会有所变化，到时我会讲清楚的。
最近公共祖先（LCA）

题目：最近公共祖先。
在最近公共祖先里，Tarjan 算法是一个离线算法。
离线算法是指在开始处理数据前，所有输入数据已知且不可更改的算法，例如离散化就是一个经典的代表。‌
众所周知，朴素 LCA 的单次查询在最坏情况下的时间复杂度为 \(O(n)\)（\(n\) 为总节点数），因此就有了改进算法，将单次查询的时间提高至 \(O(\log n)\)。
但是，能否使我们每一次对树的遍历更有价值一些呢，可不可以一次遍历获得不止一个答案甚至是所有答案呢？Tarjan 算法表示这是可以做到的。
知周所众，在以 \(u​\) 为根的子树下，任意两个不属于同一颗以 \(u​\) 的儿子为根的子树的节点（听起来有点晕），它们的 LCA 就是 \(u​\)。简单来说，设 \(\textup{son}_{u,i}​\) 表示节点 \(u​\) 的第 \(i​\) 个儿子，\(x​\) 属于 \(\textup{son}_{u,i}​\) 的子树，\(y​\) 属于 \(\textup{son}_{u,j}​\) 的子树。只要 \(i\ne j​\)，那么 \(x​\) 与 \(y​\) 的 LCA 就是 \(u​\)。

利用这一性质，我们可以想到一个做法：使用 DFS 遍历每一个节点 \(x\)，将 \(x\) 的子树存入以 \(x\) 的父亲为首的集合里面。接着枚举与 \(x\) 有关的问题（即在 DFS 开始前离线出来的问题）若问题为“求出 \(x,y\) 的 LCA”，且 \(y\) 已经被访问过了，那么这个问题的答案即为 \(y\) 的首领。
维护首领需要用到并查集，但是这个并查集其实是有点问题，他只能让节点 \(x\) 的集合变成 \(x\) 父亲节点的集合，即 fa[x] = father，而其它的操作都正常。这样做的目的是为了维护每个节点的当前最大祖先，以达到回答问题的效果。
不过为什么在问题为“求出 \(x,y​\) 的 LCA”中，答案是 find(v) 而不是 find(x) 呢？因为我们已经要求了 \(y​\) 是已经被访问过的节点了，也就是说，\(y​\) 所在的集合首领已经让 \(y​\) 成为这个集合中的一个了，而 \(x​\) 由于还在访问，所以是无法看到自己的最大祖先的。因此我们这里就选择使用 find(y) 来当答案啦！
[code]#include using namespace std;const int N = 500010, M = 2 * N;int n, m, s, a, b;vector linker[N];struct node { int v, w; };vector query[N];int fa[N], vis[N], ans[M];int find(int x) {        if (x == fa[x]) return x;        return fa[x] = find(fa[x]);}void tarjan(int x) {        vis[x] = 1; // 做访问标记         for (auto to : linker[x])                if (!vis[to]) { // 不能是自己的父亲                         tarjan(to); // 接着向下访问                         fa[to] = x; // 并查集将节点指向节点父亲                        // 注意上述两行代码不能反过来，不然它们的 fa[to] 就都是 root 了                 }        for (auto i : query[x]) {                int v = i.v, w = i.w;                // 一定要访问过，不然无意义                 if (vis[v]) ans[w] = find(v);                // find(v) 才是真答案，因为 find(v) 已经将 v 的集合首领变为 find(v) 了，而 x 还没有                // 可以这么想一想，如果 v 和 x 不属于同一颗 LCA 的儿子的子树，那么既然 v 已经访问完毕，答案肯定是 v 的集合首领         }}int main() {        cin >> n >> m >> s;        for (int i = 1; i < n; i++) {                scanf("%d%d", &a, &b);                linker[a].push_back(b);                linker.push_back(a);        }        // 离线         for (int i = 1; i > m;        for (int i = 1; i > a >> b, add(a, b);        for (int i = 1; i  n >> m;        for (int i = 1, a, b; i > a >> b;                add(a, b), add(b, a);        }        for (int i = 1; i > m;        for (int i = 1, a, b; i > a >> b;                add(a, b), add(b, a);        }        for (int i = 1; i > b;                add(a, b), add(b, a);        }        for (int i = 1; i > b;        add(a, b), add(b, a);    }    tarjan(1, -1); // 从节点1开始，初始入边编号为-1    // 计算缩点后度数：只遍历偶数索引边（每条无向边处理一次）    for (int i = 0; i < 2 * m; i += 2) {        if (bri) { // 当前无向边是桥            int u = e.u, v = e.v;            du[dcc]++; // 更新缩点后连通分量的度数            du[dcc[v]]++;        }    }    // 统计叶子节点数（度数为1的连通分量）    for (int i = 1; i > n >> m;    while (m--) {        cin >> a >> b;        e[a].push_back(b);        e.push_back(a);    }    for (root = 1; root