欢迎批评指正！
前置芝士
- 什么是强连通分量（\(\text{SCC}\)）？
强连通分量，一般指 有向图的极大强连通子图，在这些子图中，所有点双向可达。 - dfs 序：即 dfs 过程中访问点的顺序。
- dfs 生成树：由 dfs 过程中访问的边组成的边集 和 原图的点集 组成的树。
- 树边，非树边：属于 dfs 过程中访问的边 为树边，否则为非树边。
- 返祖边（反向边）：从孩子连接到祖先的边。
- 前向边：返祖边：从祖先连接到孩子的边。
- 横插边：除返祖边和前向边之外的非树边。（连接没有祖孙关系的两点的边。）
- 某个强连通分量的根：这个强连通分量重 dfs 序最小的节点。
Tarjan 算法
设两个数组 \(dfn\) 和 \(low\)，分别表示 dfs 序和仅通过 \(1\) 条非树边所能到达的点的最小 \(dfn\)。
看下面这张图：
每个节点的编号就是它的 \(dfn\)，旁边标注的数字是 \(low\)，可以自行理解一下。
另外，我们还需要一个栈 \(stk\) 存节点。
算法流程
Tarjan 是在 dfs 中实现的，每次访问到当前节点 \(u\)，就将它压入 \(stk\) 中。随后访问所有相邻的点 \(v\)。
- 如果没访问过，说明 \((u,v)\) 是一条树边，继续 dfs。
dfs \(v\) 的子树结束后，更新 \(low_u=\min(low_u,low_v)\)。
因为根据 \(low\) 的定义，走多少条树边都没关系，而 \((u,v)\) 是一条树边，我们可以从 \(u\) 走到 \(v\) 后再继续往上爬。也就是说，\(v\) 能到的 \(low_v\)，\(u\) 也能到。于是更新。 - 如果 \(v\) 已被访问过且已属于另一个 \(\text{SCC}\)，说明 \((u,v)\) 是一条横插边，两个 \(\text{SCC}\)无关，直接跳过，不予处理。
证明：因为如果当前 \(\text{SCC}\) 能访问到另一个 \(\text{SCC}\) 且我们希望两个 \(\text{SCC}\) 合并（有关），那另外那个 \(\text{SCC}\) 也应该能访问到当前 \(\text{SCC}\)，那就是说两个 \(\text{SCC}\) 是同一个，与我们的假设：“访问另一个 \(\text{SCC}\)”相悖，得证。（可能会很绕,可以先不理解。） - 如果 \(v\) 被访问过且在 \(stk\) 内，说明 \((u,v)\) 是一条返祖边，更新 \(low_u=\min(low_u,dfn_v)\)。
因为 \(low\) 的定义为仅通过 \(1\) 条非树边，故可以直接走返祖边 \((u,v)\)，如果 \(dfn_v\) 比 \(low_u\) 小，则更新。
关于为什么不是 \(low_u=\min(low_u,low_v)\)，因为 \(low_v\) 可能已经经过了一条非树边，如果再走返祖边 \((u,v)\)，就可能走了两条非树边，与 \(low\) 的定义相悖。（其实这样些也可以得到正确答案，但是求割点时就会错。）
然后判断 \(u\) 是否是根：若 \(dfn_u=low_u\)，则是当前 \(\text{SCC}\) 的根，然后退栈到 \(u\)，保存答案。
证明：
因为 \(dfn_u=low_u\)，所以 \(u\) 的子树内的所有点都不能通过返祖边到达 \(dfn\) 比 \(u\) 小的点（否则可以通过树边到达这些子节点，然后走返祖边。使 \(low_u<dfn_u\)。）
必要性：若反之 \(dfn_u>low_u\)（\(dfn_u<low_u\) 是不可能的），\(u\) 必然可以到达 \(dfn\) 更小的点,那么 \(u\) 就必然不是当前 \(\text{SCC}\) 的根。
充分性：若有 \(dfn_u=low_u\)，则 \(u\) 的子树内的点逃不出 \(u\) 的子树，无法到达 \(dfn\) 更小的点，又因为如果有 \(u\) 的子树内的点时某\(\text{SCC}\) 的根，那必然已被退栈，故退栈到 \(u\) 的那些点必然是当前 \(\text{SCC}\) 的点。
代码
代码转载自这篇大佬的博客
stack<int> stk;
// instk：是否在栈中 scc：每个点所属的强连通分量编号 cscc：强连通分量的数量
int dfsn[MAXN], low[MAXN], instk[MAXN], scc[MAXN], cnt, cscc;
void tarjan(int p)
{
low[p] = dfsn[p] = ++cnt;
instk[p] = 1;
stk.push(p); // 进栈
for (auto q : edges[p])
{
if (!dfsn[q]) // 未访问过
{
tarjan(q); // 递归地搜索
low[p] = min(low[p], low[q]);
}
else if (instk[q]) // 访问过，且q可达p
low[p] = min(low[p], dfsn[q]);
}
if (low[p] == dfsn[p]) // 发现强连通分量的根
{
int top;
cscc++;
do
{
top = stk.top();
stk.pop();
instk[top] = 0;
scc[top] = cscc; // 记录所属的强连通分量
} while (top != p); // 直到弹出p才停止
}
}