Skip to content

强连通分量 Strongly Connected Components

强连通分量指的是在有向图中的一个子图，子图任意两个节点之间都有一条路径可以到达。强连通分量只在有向图上有。

这个例子中有3个强连通分量（圆圈圈出）。

强连通分量与DFS关系：基本性质是如果一个节点\(u\)是DFS的时候访问到的当前强连通分量中的第一个节点，那么当前强连通分量会在DFS生成树中\(u\)的子树中。这个容易理解，因为强连通定义，所以强连通分量中的节点应该通过\(u\)都可到达，而因为\(u\)第一个访问，所以只能在\(u\)开始的子树中。具体有个反证法。

Tarjan算法求强连通分量

Tarjan算法就是利用上面的DFS性质来求解。考虑两个值：

  1. \(dfn_u\): 深度优先搜索遍历时结点 \(u\) 被搜索的次序。
  2. \(low_u\): 能够回溯到的最早的已经在栈中的结点的dfn值。

dfn和low可以用以下伪代码来求解：

TARJAN_SEARCH(int u)
    vis[u]=true
    low[u]=dfn[u]=++dfncnt
    push u to the stack
    for each (u,v) then do
        if v hasn't been searched then
            TARJAN_SEARCH(v) // 搜索
            low[u]=min(low[u],low[v]) // 回溯
        else if v has been in the stack then
            low[u]=min(low[u],dfn[v])

得到dfn和low之后，在回溯的过程中，判定 \(dfn_u=low_u\) 是否成立，如果成立，则栈中 \(u\) 及其上方的结点构成一个 SCC。

C++实现： 

int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc;  // 结点 i 所在 SCC 的编号
int sz[N];       // 强连通 i 的大小

void tarjan(int u) {
  low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
  for (int i = h[u]; i; i = e[i].nex) {
    const int &v = e[i].t;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (in_stack[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (dfn[u] == low[u]) {
    ++sc;
    while (s[tp] != u) {
      scc[s[tp]] = sc;
      sz[sc]++;
      in_stack[s[tp]] = 0;
      --tp;
    }
    scc[s[tp]] = sc;
    sz[sc]++;
    in_stack[s[tp]] = 0;
    --tp;
  }
}

Kosaraju算法

两次简单的DFS：

  1. 第一次 DFS，选取任意顶点作为起点，遍历所有未访问过的顶点，并在回溯之前给顶点编号，也就是后序遍历。
  2. 第二次 DFS，对于反向后的图，以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所 有未访问过的结点，选取标号最大的，重复上述过程。

复杂度\(O(n+m)\)。

// g 是原图，g2 是反图
void dfs1(int u) {
  vis[u] = true;
  for (int v : g[u])
    if (!vis[v]) dfs1(v);
  s.push_back(u);
}

void dfs2(int u) {
  color[u] = sccCnt;
  for (int v : g2[u])
    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算法，见OI-Wiki

习题