Tarjan 的本质是树形 dp。

有向图连通 - 强连通分量

例题 0：静态连通性查询

给出 \(n\) 个点 \(m\) 条边的有向图，\(q\) 次查询 \(u, v\) 问是否存在 \(u \leadsto v\)。
\(1 \leq n \leq 2\times 10^4\)，\(1 \leq m \leq 5\times 10^4\)，\(1 \leq q \leq 2\times 10^6\)。

引入

我们知道，假若图是一张 DAG，那么这个问题是简单的：我们只需要在拓扑排序时维护 std::bitset 表示可达某个点，所有点的状态，这是 \(\mathcal O(\frac{nm}w + q)\) 的。

如何把任意无向图转化为 DAG？引入「缩点」的思想：若一些点 \(S\) 是彼此均可达的，我们便把它们压缩成一个新点。容易发现，若最终的图没有任何一个点集 \(S\) 满足它们彼此均可达，那么图没有环，故转化为了 DAG。

我们想要在高效的时间内求出这个无向图缩点到最简略的情况。这时，每个点恰好属于其中的一个新点，我们称这个新点包含的原先点构成了一个极大的 强连通分量（SCC）。我们的目的可以转化为求出每个 SCC。

题解

定义：

所有有向边方向为 根到叶子 的有向树为 外向树。

所有有向边方向为 叶子到根 的有向树为 内向树。

我们考虑先对每个连通块 dfs 出若干棵外向树。随后，我们可以把边分成五类：

树边——属于外向树树上的一条边。
前向边——一条边 \(u \to v\) 满足在树上 \(u\) 是 \(v\) 的祖先。
反向边——一条边 \(u \to v\) 满足在树上 \(v\) 是 \(u\) 的祖先。
横叉边——一条边 \(u \to v\) 满足 \(u, v\) 在同一棵树上但没有祖先关系。
无用边——一条边 \(u \to v\) 满足 \(u, v\) 不在同一棵树上。

我们考虑，因为 SCC 的首要条件是联通，那么在每棵 dfs 树上我们将会选取若干个相邻的点组成一个 SCC 连通块。这也就是说，断掉若干的点向 dfs 树上父亲的连边。

我们具体考虑每种非树边对 SCC 带来的影响。前向边不会影响连通性，忽略；由于 dfs 的访问特性，无用边在任何两个 SCC 间肯定只存在一次（也就是说，不会构成任何环），可以进行忽视。

所以，我们聚焦于反向边和横叉边。我们设 \(low_u\) 表示 \(u\) 在树上经过 \(\leq 1\) 个 反向边或横叉边（一般称为非树边） 所能到达的 能到达点 \(\bm u\) 的所有点中 \(\text{dfn}\) 序的最小值。初始化 \(low_u = \text{dfn}(u)\)。

我们如何更新 \(low\)？发现我们遍历每条树边出边 \(u \to v\)，用 \(low_v\) 更新 \(low_u\)；遍历非树边出边 \(u \to v\)，若 \(\bm v\) 可达 \(\bm u\) 则 用 \(\text{dfn}(v)\) 更新 \(low_u\)。一个简略的写法是不显式建出 dfs 树，而是在 dfs 的过程中同时对 \(low\) 进行 dp。

我们把 \(low\) 求出来以后呢？注意到若 \(low_u = u\)，那么 \(u\) 的子树任意点并不能到达 \(u\) 的祖先，因此应断掉 \(fa_u \to u\) 的边，而这也是在 dfs 过程中可以一并维护的。

如何维护可达性？我们可以采用一个栈，依次存放 当前的「被访问到但未被标入 SCC」的点。在 dfs 过程中，若遇到一个点 \(low_u = u\)，那么把栈顶一直到 \(u\) 放入一个新的 SCC 里；这样，只需判断 \(v\) 是否在栈内，就可以知道是否 \(v\) 可达当前 \(u\) 了。

时间复杂度 \(\mathcal O(n + m)\)。最后回到原问题，套用 DAG 做法即可。

代码

#define MAXN 100001
std::vector<int> e[MAXN], f[MAXN];
int a[MAXN], scc[MAXN], dfn[MAXN], low[MAXN], cntD = 0, cntS = 0;
bool vis[MAXN];
std::stack<int> st;
void Tarjan(int u) {
    vis[u] = true, dfn[u] = low[u] = ++cntD, st.push(u);
    for (int v : e[u]) {
        if (!dfn[v]) Tarjan(v), low[u] = std::min(low[u], low[v]); // 树边
        else if (vis[v]) low[u] = std::min(low[u], dfn[v]); // 非树边
    }
    if (low[u] == dfn[u]) {
        for (int t = 0, q = ++cntS; t != u; )
            scc[t = st.top()] = q, vis[t] = false, st.pop();
    }
}