强连通分量

简介 #

强连通 #

在有向图 $G$ 中，如果同时存在 $u→v$ 和 $v→u$ 的路径，那么称 $u$ 和 $v$ 强连通.

强连通图 #

如果有向图 $G$ 的任意两个节点都强连通，那么称 $G$ 是强连通图.

强连通分量 #

如果图 $G$ 的子图是强连通图，那么该子图称作 $G$ 的强连通分量.

本章介绍求强连通分量的三种算法.

Tarjan 算法 #

图的结构 #

Tarjan 算法基于对图的深度优先遍历（DFS），并且将图近似地看成一棵树.因此，这棵树中会不可避免地出现一些奇怪的边.

前向边：与普通边方向一致，但跨越多个节点.
返祖边：与普通边方向相反，从子孙指向祖先.
横向边：边的两个端点居于树的同一深度.

时间戳 #

DFS 遍历一张图时，按访问顺序给节点打标记.$u$ 是第 $i$ 个被访问的节点，记作 $dfn[u]=i$.这个标记叫做「时间戳」.在图中，时间戳标记在节点的右上方.

$u$	$1$	$2$	$3$	$4$	$5$	$6$
$dfn[u]$	$1$	$2$	$5$	$3$	$4$	$6$

追溯值 #

Tarjan 算法还引入了「追溯值」：$low[u]$，定义为以下节点时间戳的最小值：

以 $u$ 为根的子树中的所有节点.
从这棵子树的任意节点出发，经过 $1$ 条前向边、返祖边或横向边，能到达的节点.

以 $low[2]$ 为例，其子树中有 $2,4,5$ 号节点，还可以通过一条返祖边到达 $1$ 号节点.$low[2]$ 为这些节点时间戳的最小值，也就是 $1$.

$u$	$1$	$2$	$3$	$4$	$5$	$6$
$low[u]$	$1$	$1$	$5$	$1$	$4$	$6$

基本原理 #

Tarjan 算法是如何利用 $dfn$ 和 $low$ 来求强连通分量的呢？

首先，强连通分量中必然存在环，也就必然存在返祖边.
如果节点 $u$ 满足 $dfn[u]=low[u]$，存在两种情况：
- 如果 $u$ 没有出边，则 $u$ 独自为一个强连通分量.
- 否则 $u$ 的子树中必有一条返祖边指向 $u$ 本身，此处必存在多节点的强连通分量.

要想具体地确定哪些节点是强连通分量，还得借助栈.具体看以下样例.

$dfn[1]=low[1]=1$.

$u$	$1$	$2$	$3$	$4$	$5$	$6$
$dfn[u]$	$1$
$low[u]$	$1$

$dfn[2]=low[2]=1$.

$u$	$1$	$2$	$3$	$4$	$5$	$6$
$dfn[u]$	$1$	$2$
$low[u]$	$1$	$2$

$dfn[4]=low[4]=3$.节点 $4$ 有一条返祖边指向 $1$，故更新 $low[4]=low[1]=1$.

$u$	$1$	$2$	$3$	$4$	$5$	$6$
$dfn[u]$	$1$	$2$		$3$
$low[u]$	$1$	$2$		$\textcolor{red}{1}$

回溯至节点 $2$，更新 $low[2]=\min(low[2],low[4])=1$.

$u$	$1$	$2$	$3$	$4$	$5$	$6$
$dfn[u]$	$1$	$2$		$3$
$low[u]$	$1$	$\textcolor{red}{1}$		$1$

$dfn[5]=low[5]=4$.节点 $5$ 没有出边和子树，单独一个节点构成强连通分量.移除栈顶的 $5$.

$u$	$1$	$2$	$3$	$4$	$5$	$6$
$dfn[u]$	$1$	$2$		$3$	$\textcolor{red}{4}$
$low[u]$	$1$	$1$		$1$	$\textcolor{red}{4}$

回溯至节点 $2$，$low[2]=\min(low[2],low[5])=1$.

$u$	$1$	$2$	$3$	$4$	$5$	$6$
$dfn[u]$	$1$	$2$		$3$	$4$
$low[u]$	$1$	$1$		$1$	$4$

回溯至节点 $1$，$low[1]=\min(low[1],low[2])=1$.此时 $low[1]=dfn[1]$，栈顶的红色部分同属一个强连通分量.将其从栈中删除.

$u$	$1$	$2$	$3$	$4$	$5$	$6$
$dfn[u]$	$\textcolor{red}{1}$	$2$		$3$	$4$
$low[u]$	$\textcolor{red}{1}$	$1$		$1$	$4$

…

时间复杂度为 $O(n+m)$（$n$ 为点数，$m$ 为边数）.

// ans: 强连通分量个数
const int N = 1e6;
int dfn[N], low[N], tot, ans;
int in[N]; // u 号节点在第 in[u] 个强连通分量
vector<int> g[N]; // g[u]: u 指向的节点集合
stack<int> s;

void tarjan(int u) {
    dfn[u] = low[u] = ++ tot;
    s.push(u);
    for(int i = 0; i < g[u].size(); i ++) {
        int v = g[u][i];
        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if(!in[u])
            low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]) {
        in[u] = ++ ans;
        while(s.top() != u) // 栈顶到 u 这部分的节点在同一个强连通分量
            in[s.top()] = ans, s.pop();
        s.pop();
    }
}

Kosaraju 算法 #

Kosaraju 的核心思想可以总结为两点：

强连通分量反过来还是强连通分量.
把强连通分量反一半过来会得到两条共起点、终点的路径.

第一次正向遍历，第二次反向遍历，若出现共起点、终点的两条路径，则此处必有强连通分量.

const int N = 1e6;
int sccCnt, color[N], vis[N];
vector<int> g[N];  // g[u]:  u 指向的节点集合
vector<int> g2[N]; // g2[u]: 指向 u 的节点集合（反图）
vector<int> s;

void dfs1(int u) {
    vis[u] = true;
    for(int i = 0; i < g[u].size(); i ++) {
        int v = g[u][i];
        if(!vis[v]) dfs1(v);
    }
    s.push_back(u);
}

void dfs2(int u) {
    color[u] = sccCnt;
    for(int i = 0; i < g2[u].size(); i ++) {
        int v = g2[u][i];
        if(!color[v]) dfs2(v);
    }
}

void kosaraju() {
    sccCnt = 0;
    for(int i = 1; i <= n; i ++)
        if(!vis[i]) dfs1(i);
    for(int i = n; i >= 1; i --) {
        if(!color[s[i]]) {
            ++ sccCnt;
            dfs2(s[i]);
        }
    }
}

Garbow 算法 #

未完待续 …

int garbow(int u) {
    stack1[++p1] = u;
    stack2[++p2] = u;
    low[u] = ++dfs_clock;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (!low[v])
            garbow(v);
        else if (!sccno[v])
            while (low[stack2[p2]] > low[v]) p2--;
    }
    if (stack2[p2] == u) {
        p2--;
        scc_cnt++;
        do {
            sccno[stack1[p1]] = scc_cnt;
        } while (stack1[p1--] != u);
    }
    return 0;
}

void find_scc(int n) {
    dfs_clock = scc_cnt = 0;
    p1 = p2 = 0;
    memset(sccno, 0, sizeof(sccno));
    memset(low, 0, sizeof(low));
    for (int i = 1; i <= n; i++)
        if (!low[i]) garbow(i);
}