强连通分量（Strongly Connected Components）
时间：2019.8.1
使用 Tarjan 算法来求解强连通分量问题。强连通分量是在有向图上定义的。我们会将每个强连通分量染上不同的颜色。这样就可以得到缩点后的 DAG。
先介绍有向图遍历中的四种边。
四种边
-
树边：有向图遍历中 DFS 树上的边称为树边。
-
前向边：有些边从子树的根连向子树中的某个节点。这样的边称为前向边。
-
返祖边：连向当前点祖先的边称为返祖边（有的文献中称为“后向边”）
-
横叉边：从一棵子树连向另一棵子树的边为横叉边。注意被连接（箭头末端）的子树要更先被遍历。
以上 4 中边中，前两种连向的点的 DFS 序要更大；后两种连向的点的 DFS 序更小。除了第一种树边之外，剩下三种边连向的点都已被访问过，不需递归 DFS 函数。
dfn 和 low
Tarjan 算法维护一个栈，存储可能是当前强连通分量中的点。已经确定的和还未被访问的节点不会出现在栈中。下面称栈中的节点为“栈点”，不在栈中的节点为“非栈点”。
为每个节点保存两个值 \(dfn\) 和 \(low\)。分别定义如下：
\(dfn[u]\) 表示节点 \(u\) 的 DFS 序。这个值在第一次访问 \(u\) 的时候就已确定。
-
\(low[u]\) 表示从节点 \(u\) 的子树中仅通过一条有向边所能够到达的栈点的 \(dfn\) 最小值，以及这个子树中节点的 \(dfn\) 最小值（其实就是 \(dfn[u]\)），的最小值（请将这句有点拗口的话再读一遍 qwq）。
但是！请注意一定是到达一个栈点，而不是非栈点。