有向图上的Tarjan

前言

本篇博文仅仅用来当作个人的学习笔记，创作的标准是让本人自己理解即可，不推荐当作读者的学习资料，如想学习 DAG 上的 Tarjan 算法建议上网搜索详细的资料。

Intro

先约定好几个定义哈：

1. 强连通分量（scc）：表示在图上最大的一个子集，满足这个子集中所有点两两间可以相互连通。
2. 流图：在一个 DAG 里，如果存在一个点 $\operatorname{start}$，从这个点出发可以到达所有点，称此图为流图。
3. 搜索树：在一个流图上从 $\operatorname{start}$ 开始深度优先遍历时所有发生递归的边构成一颗以 $\operatorname{start}$ 为根的树，称其为流图的搜索树。
4. dfn：时间戳嘛。
5. 后向边：搜索树上从一个后代指向前代的边。
6. 前向边：搜索树上一个从前代指向后代的边。
7. 树枝边：搜索树中的边。
8. 横叉边：除上述以外所有的边。

我们怎么求出强连通分量呢？

基本思路：对于每个点，尽量找到与它一起能构成环的所有节点。

实现

执行深度优先遍历，同时开一个栈，访问到 $x$ 时，栈中记录以下节点：

1. 搜索树上 $x$ 的祖先节点。
2. 已经访问过，并且存在一条边到 $x$ 的祖先节点的边的节点。

说白了，栈中的节点就是能与从 $x$ 出发的后向边和横叉边形成环的节点。

再引入一个追溯值：在以 $x$ 为根的子树中，$\operatorname{low_x}$ 表示满足以下条件的节点的最小时间戳：

1. 该点存在栈中。
2. 存在一条从以 $x$ 为根的子树中出发的有向边以该节点为终点。

如果一个节点还未被访问，直接去访问， $\operatorname{low_x} = \min{\operatorname{low_x},\operatorname{low_y}}$。

如果被访问了，并且该节点还在栈中，$\operatorname{low_x} = \min{\operatorname{low_x}, \operatorname{dfn_y}}$。

如果找到一个 $\operatorname{low_x} = \operatorname{dfn_x}$ 的点，说明你找到了一个强连通分量，然后打上标记，记录一下就好了。

void tarjan(int u) {
    dfn[u] = low[u] = ++num;
    st[++top] = u, is[u] = true;

    for(int i = lk[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if(is[v]) low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]) {
        ++cnt;
        int v;
        do {
            v = st[top--], is[v] = false;
            c[v] = cnt;
        } while(u != v);
    }
}

例题不给了。