强连通分量(CSS)

Posted on Edited on In Word count in article: 256 Reading time ≈ 1 mins.
强连通分量入门

前置芝士

强连通：有向图 \(G\) 中任意两个节点相连

\(DFS\) 树：

  • 树边（\(tree\;edge\)）：搜索到为访问的点
  • 返祖边（\(back\;tree\)）：指向祖先节点，亦称回边
  • 横叉边（\(cross\;edge\)）：搜索到并非祖先节点的已访问的节点
  • 前向边（\(forward\;edge\)）：搜索到子树中的节点

\(Tarjan\) 求 \(SCC\)

定理：一个 \(SCC\) 一定存在于以 \(G\) 为根的子树中，其中 \(G\) 是这个 \(SCC\) 中的一个点

在该算法中需要维护以下几个变量：

  • \(dfn_u\)：在搜索过程中结点 \(u\) 的搜索次序
  • \(low_u\)：在 \(u\) 的子树中能回溯到的最早的已在栈中的结点

容易发现，当 \(dfn_u\;=\;low_u\) 时，一定存在一个 \(SCC\)

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void Tarjan(int u)
{
    Low[u] = Dfn[u] = ++Tim;
    Stac[++Top] = u, Vis[u] = 1;
    for (auto v : edge[u])
    {
        if (!Dfn[v])
        {
            Tarjin (v);
            Low[u] = min(Low[u], Low[v]);
        }
        else if (Vis[v])Low[u] = min(Low[u], Dfn[v]); //前向边
    }
    
    if (Dfn[u] == Low[u])
    {
        Tot++;
        while(Stac[Top + 1] != u)
        {
            Color[Stac[Top]] = Tot;
            Vis[Stac[Top--]] = 0;
            Sum[Tot]++;
        }
    }
}