[算法学习笔记] 强连通分量
DFS生成树
在介绍强连通分量前，我们先来了解一下DFS生成树。
一棵DFS生成树分为树边，前向边，返祖边（一说反向边），横叉边。我们来画图解释一下：
在这棵DFS生成树中，黑色为树边，它是在DFS遍历时获得的，红色为返祖边，顾名思义，从儿子指向父亲或祖先。蓝色为横叉边，它是在搜索的时候遇到子树中的节点的时候形成的。粉色是前向边，它是在搜索的时候遇到子树中的结点的时候形成的。
强连通分量
强连通分量，具有强连通性，极大性。强连通性顾名思义，在一个强连通分量内的节点都是可以直接或间接互相可达的。极大性指一个强连通分量内不能再加入任何一个节点，再加入任何一个节点都不满足强连通性。
强连通分量一般在有向图中讨论，若在无向图中强连通分量就退化成了连通块。
为了更好的理解强连通分量，我们画图举例：
在这张图中，有两个强连通分量，分别是\({1,2,3}\)和\({1,5,6}\)。由此我们发现一个点可以同属于两个不同的强连通分量。
Tarjan
求强连通分量的方法有很多，参照OI-wiki，这里主要介绍最常见的Tarjan算法。
在讲解Tarjan 算法求强连通分量前，我们定义：
- \(dfn_u\) 表示节点\(u\)被dfs遍历时的顺序编号
- \(low_u\) 表示节点\(u\)经过若干条树边，最多经过一条返祖边能到达的\(dfn\)值最小的点
我们发现，在一个强连通分量中，有且只有一个节点的\(dfn\)值等于\(low\)值，这个节点同时也是一个强连通分量中被最先dfs遍历到的点，也就是\(dfn\)值最小的点。我们不妨将这个节点定义为一个强连通分量中的祖先。在接下来的Tarjan过程中会用到这个重要的性质。
\(low\)值可以在dfs的同时得到，对于一条边\(u-v\),如果：
-
\(v\)还未访问，则\(low\)值还不能确定，所以先dfs \(v\)，再用\(low_v\)更新\(low_u\)，因为\(u,v\)是一条边，\(v\)能到达的点\(u\)也一定可以。
-
\(v\)已经访问，且\(v\)能到达\(u\)，我们发现如果出现这种情况若可以更新\(low_u\)则\(u-v\)是返祖边，故用\(dfn_v\)更新\(low_u\)。
-
\(v\)已经访问，但\(v\)不能到达\(u\),不做处理。
那么我们如何确定\(v\)能否到达\(u\)呢？
容易发现需要判定\(v\)能否到达\(u\)的时候属于上文第二种情况，即出现返祖边。我们可以在dfs的时候维护一个栈，每次dfs将当前节点压入栈，这样判定\(v\)能否到达\(u\)的时候我们只需要判定\(u\)是否在栈中就可以了。
我们现在求出了每个节点的\(low\)值，如何求强连通分量呢？
这里就用到了前面所提到的性质，在一个强连通分量中，有且仅有一个节点的\(dfn\)值等于\(low\)值，这个节点也是一个强连通分量中\(dfn\)值最小的点，我们称之为一个强连通分量的祖先。因此，在回溯的时候只需要判断该节点的\(dfn\)值是否等于\(low\)值，如果相等则证明该节点是一个强连通分量的祖先，那么在栈中祖先节点以上的点都属于该强连通分量，循环出栈，统计答案+1即可。
强连通分量一般和缩点连用，由于强连通分量的极大性，若对强连通分量进行缩点，显然变成了有向无环图。（若有环则不满足极大性，也就是说两个强连通分量还能合并成一个新的强连通分量，显然不可）。
缩完点后的强连通分量由于变成了DAG，所以可以dp，可以最短路。