【图论】—— 有向图的强连通分量
https://img-blog.csdnimg.cn/eff3f69ad01d479c8948c3429a2bfdf9.png给定有向图 https://latex.codecogs.com/gif.latex?%5Csmall%20G%3D%28V%2CE%29 ，若存在 https://latex.codecogs.com/gif.latex?%5Csmall%20r%20%5Cepsilon%20V，满足从 https://latex.codecogs.com/gif.latex?%5Csmall%20r 出发能到达 https://latex.codecogs.com/gif.latex?%5Csmall%20V 中所有的点，则称 https://latex.codecogs.com/gif.latex?%5Csmall%20G 是一个“流图”（ Flow Graph ），记为 https://latex.codecogs.com/gif.latex?%5Csmall%20%28G%2Cr%29 ，其中，https://latex.codecogs.com/gif.latex?%5Csmall%20r 称为流图的源点。
在一个流图 https://latex.codecogs.com/gif.latex?%5Csmall%20%28G%2Cr%29 上从 https://latex.codecogs.com/gif.latex?%5Csmall%20r 进行深度优先遍历，每个点只访问一次。所有发生递归的边 https://latex.codecogs.com/gif.latex?%5Csmall%20%28x%2Cy%29 （换言之，从 https://latex.codecogs.com/gif.latex?%5Csmall%20x 到 https://latex.codecogs.com/gif.latex?%5Csmall%20y 是对 https://latex.codecogs.com/gif.latex?%5Csmall%20y 的第一次访问）构成一棵以 https://latex.codecogs.com/gif.latex?%5Csmall%20r 为根的树，我们把它称为流图 https://latex.codecogs.com/gif.latex?%5Csmall%20%28G%2Cr%29 的搜索树。
同时，在深度优先遍历的过程中，按照每一个节点第一次被访问的时间顺序，依次给予流图中 N 个节点 1~N 的整数标记，称为时间戳，记为 https://latex.codecogs.com/gif.latex?%5Csmall%20dfn%5Bx%5D。
流图中的每条有向边 https://latex.codecogs.com/gif.latex?%5Csmall%20%28x%2Cy%29 必然是以下四种之一：
[*]树枝边，指搜索树中的边，即 https://latex.codecogs.com/gif.latex?%5Csmall%20x 是 https://latex.codecogs.com/gif.latex?%5Csmall%20y 的父节点
[*]前向边，指搜索树中 https://latex.codecogs.com/gif.latex?%5Csmall%20x 是 https://latex.codecogs.com/gif.latex?%5Csmall%20y 的祖宗节点
[*]后向边，指搜索树中 https://latex.codecogs.com/gif.latex?%5Csmall%20y 是 https://latex.codecogs.com/gif.latex?%5Csmall%20x 的祖宗节点
[*]横叉边，指除了以上三种情况之外的边，它一定满足 https://latex.codecogs.com/gif.latex?%5Csmall%20dfn%5By%5D%20%3C%20dfn%5Bx%5D
如下图“流图”以及其搜索树所示：
加粗的表示的是树枝边，并构成一棵搜索树。
https://img-blog.csdnimg.cn/b297403898144d719e899961a5a12d03.png
有向图的强连通分量
给定一张有向图。若对于图中的任意两个结点 https://latex.codecogs.com/gif.latex?%5Csmall%20x%2Cy，既存在从 https://latex.codecogs.com/gif.latex?%5Csmall%20x 到 https://latex.codecogs.com/gif.latex?%5Csmall%20y 的路径，也存在从 https://latex.codecogs.com/gif.latex?%5Csmall%20y 到 https://latex.codecogs.com/gif.latex?%5Csmall%20x 的路径，则称该有向图是“强连通图”。
有向图的极大连通子图称为“强连通分量”，简记为 SCC(Strongly Connected Component)。
此处的“极大”的含义和双连通分量的“极大”的含义类似。
Tarjan算法基于有向图的深度优先遍历，能够在线性的时间里求出一张有向图的强连通分量。
一个“环”一定是强连通图。如果既存在从 https://latex.codecogs.com/gif.latex?%5Csmall%20x 到 https://latex.codecogs.com/gif.latex?%5Csmall%20y的路径， 也存在从 https://latex.codecogs.com/gif.latex?%5Csmall%20y 到 https://latex.codecogs.com/gif.latex?%5Csmall%20x 的路径，那么 https://latex.codecogs.com/gif.latex?%5Csmall%20x%2Cy 显然在一个环中。因此，Tarjan算法的基本思路就是对每个点，尽量找到与它一起能够构成环的所有节点。
容易发现，“前向边” https://latex.codecogs.com/gif.latex?%5Csmall%20%28x%2Cy%29 没有什么用处，因为搜索树上本来就存在 从 https://latex.codecogs.com/gif.latex?%5Csmall%20x 到 https://latex.codecogs.com/gif.latex?%5Csmall%20y的路径。
“后向边” https://latex.codecogs.com/gif.latex?%5Csmall%20%28x%2Cy%29 非常有用，因为它可以从搜索树上 从 https://latex.codecogs.com/gif.latex?%5Csmall%20y 到 https://latex.codecogs.com/gif.latex?%5Csmall%20x 的路径一起构成环。
“横向边” https://latex.codecogs.com/gif.latex?%5Csmall%20%28x%2Cy%29 视情况而定，如果从 https://latex.codecogs.com/gif.latex?%5Csmall%20y 出发能够找到一条回到 https://latex.codecogs.com/gif.latex?%5Csmall%20x 的祖宗节点，那么 https://latex.codecogs.com/gif.latex?%5Csmall%20%28x%2Cy%29 就是有用的。
为了找到通过“后向边”和“横叉边”构成的换，Tarjan算法在深度优先遍历的同时维护一个栈。
当访问到结点 x 时，栈中需要保存以下两类节点：
[*]搜索树上 x 的祖宗节点，记为集合 https://latex.codecogs.com/gif.latex?%5Csmall%20anc%28x%29
设 https://latex.codecogs.com/gif.latex?%5Csmall%20y%5Cepsilon%20anc%28x%29 。若存在后向边 https://latex.codecogs.com/gif.latex?%5Csmall%20%28x%2Cy%29 ，则 https://latex.codecogs.com/gif.latex?%5Csmall%20%28x%2Cy%29 与 y 到 x 的路径一起形成环。
[*]已经访问过，并且存在一条路径到达 https://latex.codecogs.com/gif.latex?%5Csmall%20anc%28x%29 的节点
设 z 是一个这样的点，从 z 出发存在一条路径到达 https://latex.codecogs.com/gif.latex?%5Csmall%20y%5Cepsilon%20anc%28x%29 。若存在横叉边 https://latex.codecogs.com/gif.latex?%5Csmall%20%28x%2Cz%29 ，则https://latex.codecogs.com/gif.latex?%5Csmall%20%28x%2Cz%29 、z 到 y 的路径、y 到 x 的路径构成一个环。
综上所述，栈中的节点就是能与从 x 出发的“后向边”和“横叉边”形成环的节点。进而可以引入“追溯值”的概念。
追溯值
设 https://latex.codecogs.com/gif.latex?%5Csmall%20subtree%28x%29 表示流图的搜索树中以 x 为根的子树。x 的追溯值 https://latex.codecogs.com/gif.latex?%5Csmall%20low%28x%29 定义为满足以下条件的节点的最小时间戳：
[*]该点在栈中
[*]存在一条从 https://latex.codecogs.com/gif.latex?%5Csmall%20subtree%28x%29出发的有向边，以该点为终点
根据定义，Tarjan算法按照以下步骤计算“追溯值”：
[*]当节点 x 第一次被访问时，把 x 入栈，初始化 https://latex.codecogs.com/gif.latex?%5Csmall%20low%5Bx%5D%20%3D%20dfn%5Bx%5D
[*]扫描从 x 出发的每一条边 https://latex.codecogs.com/gif.latex?%5Csmall%20%28x%2Cy%29
[*]若 y 没有被访问过，则说明 https://latex.codecogs.com/gif.latex?%5Csmall%20%28x%2Cy%29 是“树枝边”，递归访问 y ，从 y 回溯后，令https://latex.codecogs.com/gif.latex?%5Csmall%20low%5Bx%5D%3Dmin%28low%5Bx%5D%2Clow%5By%5D%29
[*]若 y 被访问过且 y 在栈中，则令 https://latex.codecogs.com/gif.latex?%5Csmall%20low%5Bx%5D%20%3D%20min%28low%5Bx%5D%2Cdfn%5By%5D%29
[*]从 x 回溯之前，判断是否有 https://latex.codecogs.com/gif.latex?%5Csmall%20low%5Bx%5D%3Ddfn%5Bx%5D 。若成立，则不断从栈中弹出节点，直至 x 出栈
下页图中的中括号【】里的数值标注了每个节点的的“追溯值”https://latex.codecogs.com/gif.latex?%5Csmall%20low
https://img-blog.csdnimg.cn/d8a37a71d7ab4f5c9f5653fc073d104c.png
强连通分量判定法则
在追溯值的计算过程中，若从 x 回溯前，有 https://latex.codecogs.com/gif.latex?%5Csmall%20low%5Bx%5D%20%3D%20dfn%5Bx%5D 成立，则栈中从 x 到 栈顶的所有节点构成一个强连通分量。
大致来说，在计算追溯值的第三步，如果 https://latex.codecogs.com/gif.latex?%5Csmall%20low%5Bx%5D%20%3D%20dfn%5Bx%5D ，那么说明 https://latex.codecogs.com/gif.latex?%5Csmall%20subtree%28x%29 中的节点不能与栈中其他结点一起构成环。另外，因为横叉边的终点时间必然小于起点时间戳，所以https://latex.codecogs.com/gif.latex?%5Csmall%20subtree%28x%29中的结点也不可能直接到达尚未访问的结点（时间戳更大）。综上所述，栈中从 x 到栈顶的所有节点不能与其他结点构成环。
由因为我们及时进行了判定和出栈操作，所以从 x 到栈顶的所有节点独立构成一个强连通分量。
Tarjan算法模板
void tarjan(int u)
{
dfn = low = timestamp;
stk[++ top] = u, in_stk = true;
for(int i = h; ~i; i = ne)
{
int j = e;
if(!dfn)
{
tarjan(j);
low = min(low, low);
}
else if(in_stk)
low = min(low, dfn)
}
if(dfn == low)
{
int y;
++ scc_cnt;
do{
y = stk;
in_stk = false;
id = scc_cnt;
}while(y != u)
}
} 缩点
我们可以把每一个 SCC 缩成一个点。对于原图中的每条有向边 https://latex.codecogs.com/gif.latex?%5Csmall%20%28x%2Cy%29 若 https://latex.codecogs.com/gif.latex?%5Csmall%20id%5Bx%5D%5Cneq%20id%5By%5D ，则在编号为 https://latex.codecogs.com/gif.latex?%5Csmall%20id%5Bx%5D 与编号为 https://latex.codecogs.com/gif.latex?%5Csmall%20id%5By%5D 的SCC之间连边。
最终，我们会得到一个有向无环图（DAG）
for(int x = 1; x
页:
[1]