环的寻找：Tarjan算法

在图论中，强连通图和强连通分量是针对有向图的重要概念。它们描述了图中节点之间的可达性和结构特性。

SCC的具体应用见差分约束系统、SPFA最短路、SCC缩点

强连通图 (SCG)

定义： 如果有向图中任意两个节点之间都存在双向路径（即从节点A到节点B和从节点B到节点A都有路径），则称该图为强连通图。 关键点：

1. 双向可达性：每个节点都能到达其他所有节点。
2. 整体性质：强连通性是图的整体性质，而非局部性质。
3. 示例：
   • 一个环图（如节点1→2→3→1）是强连通的。
   • 城市中的单向道路网络若构成强连通图，则任意两个地点之间可以互相到达。

强连通分量 (SCC)

定义： 有向图的极大强连通子图称为强连通分量（SCC）。

• 极大：若再加入任何其他节点，该子图将不再强连通。 关键点：

1. 局部结构：强连通分量是图的局部结构，将图分解为多个“强连通块”。
2. 分解特性：每个节点恰好属于一个SCC，不同SCC之间的边是单向的（否则可合并为更大的SCC）。

强连通图 vs 强连通分量

Tarjan 算法（寻找最大 SCC）

时间戳的引入

Tarjan 算法的核心是通过深度优先搜索（DFS）过程中的时间戳来识别强连通分量。具体通过两个数组记录关键信息：

• $ \text{dfn}[u] $：记录节点 $ u $ 被首次访问的时间戳（即 DFS 遍历的顺序编号），每个节点仅在首次访问时赋值，且唯一。
• $ \text{low}[u] $：记录节点 $ u $ 能回溯到的最早时间戳（即 $ u $ 所在的连通分支中最小的 $ \text{dfn} $ 值）。

全局变量 timestamp：用于递增记录访问顺序，初始值为 0，每访问一个新节点则自增 1。

变量说明

• inStack[N]：布尔数组，标记节点是否在栈中（用于区分已处理和未处理的节点）。
• stack<int> st：存储当前 DFS 路径上的节点，用于在找到 SCC 时提取其中的所有节点。
• vector<int> g[N]：邻接表，存储有向图的边。
• scc[N]：记录每个节点所属的强连通分量编号。
• sz[N]：记录每个强连通分量包含的节点数量。
• cnt：强连通分量的计数器，每找到一个新的 SCC 则自增 1。

算法执行步骤

1. DFS 遍历

对每个未访问的节点 $ u $ 执行 dfs(u)：

• 将 $ u $ 入栈，标记 $ \text{inStack}[u] = \text{true} $，并初始化：

  $$ \text{dfn}[u] = \text{low}[u] = ++\text{timestamp} $$

• 遍历 $ u $ 的所有邻接节点 $ v $：

  • 若 $ v $ 未被访问（即 $ \text{dfn}[v] = 0 $），递归执行 dfs(v)，回溯时更新：

    $$ \text{low}[u] = \min(\text{low}[u], \text{low}[v]) $$

  • 若 $ v $ 已在栈中（即 $ \text{inStack}[v] = \text{true} $），说明 $ v $ 是当前路径上的节点，更新：

    $$ \text{low}[u] = \min(\text{low}[u], \text{dfn}[v]) $$

2. 判断 SCC

当满足 $ \text{dfn}[u] = \text{low}[u] $ 时，说明 $ u $ 是一个 SCC 的根节点：

• 从栈中弹出节点直到 $ u $ 被弹出，这些节点构成一个强连通分量；

• 对每个弹出的节点 $ x $：

  • 标记 $ \text{inStack}[x] = \text{false} $

  • 设置：

    $$ scc[x] = cnt, sz[cnt]+=1 $$

• 最后将 cnt 自增 1，完成一个 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
26
27
28
29
30
31
32
33
34
35
36
37

int inStack[N];
int dfn[N],low[N];
stack<int> st;
vector<int> g[N];
int scc[N],sz[N];
int timestramp;
int cnt;
void dfs(int u)
{
    st.push(u);
    low[u] = dfn[u] = ++timestramp;
    inStack[u] = true;
    for(auto v : g[u])
    {
        if(!dfn[v])
        {
            dfs(v);
            low[u] = min(low[v],low[u]);
        }
        else if(inStack[v])
            low[u] = min(low[v],low[u]);
    }

    if(dfn[u]==low[u])
    {
        cnt++;
        int y;
        do
        {
            y = st.top();
            inStack[y] = false;
            scc[y] = cnt;
            sz[cnt]++;
            st.pop();
        }while(y!=u);
    }
}