有向图的强连通分量

定义：

给定一张有向图。若对于图中任意两个节点，既存在从到的路径，也存在从到的路径，则称该有向图是 “强连通图” 。有向图的极大强连通子图被称为 “强连通分量“，简记为。

如图，红色部分即为一个。

Tarjan算法：

实现原理：

1. 处理参数：

对于每一个点，其都有两个参数和

定义：

：遍历到点时的时间戳
：点可到达的值最小的点

求出参数：

对该图进行一遍，使得该图中每个点都被遍历到且仅被遍历一次

在进行时：

遍历每个点的同时都将其压入栈中

对于：我们为每一个点赋予一个时间戳（即时的次序），并将其记录在中

对的值有两种情况：

假设点的子节点为

当点已经被遍历过时：则判断是否在栈中（是否为所在的的一部分）若在则将更新为（为了防止 $横插边 ①$ 将连向值较小的点）

当点未被遍历过时：将更新为

①横插边：对于图中的一条边，如果满足不是的祖先，则边为一条横插边。横插边一定满足

2. 找出SCC：

判定：

设当前遍历到点，则当时，在栈中的所有点即为一个强连通分量的所有点

证明：

当时，点无法在向值更小的地方走，而点是栈中的除外的所有节点的子孙节点，且点是可以走到点的

这说明从点出发一定可以经过栈中除外的所有节点在回到，即栈中的所有结点构成了一个环

而环一定满足的定义

所以判定成立

Code:

int n, m;
int h[N], e[M], ne[M], idx;     // 链式前向星存图
int dfn[N], low[N], timestamp;  // 两个参数和时间戳记录
int id[N], scc_cnt;             // SCC编号和计数
int stk[N], top;                // 栈
bool in_stk[N];                 // 记录是否在栈中

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;
    
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if(in_stk[j]) low[u] = min(low[u], dfn[j]);
    }
    
    if(dfn[u] == low[u])
    {
        int y;
        ++ scc_cnt;           // SCC的个数增加
        do {
            y = stk[top -- ]; // 将满足条件的数全部弹出, 加入到新的SCC中
            in_stk[y] = false;
            id[y] = scc_cnt;
            siz[scc_cnt] ++ ;
        } while(y != u);      // 直到再次回到u为止(这说明环上的点已经全部弹出)
    }
}

在 main()中要保证最后所有点的都不为零

所以有代码：

1 2	for(int i = 1; i <= n; i ++ ) if(!dfn[i]) tarjan(i);

应用：缩点

定理：

由所有组成的图一定是一张拓扑图（即有向无环图，简称）

而且编号的倒序一定是拓扑序

证明：

如图，分为两种情况讨论：

先遍历子图：这种情况一定会在某个地方断掉（如边），之后的是该子图缩点后的祖先节点，满足定理
先遍历子图：这种情况会一次遍历所有点，该子图缩点后为之后的的祖先节点，满足定理

所以定理成立

firstlight's world