强连通分量

概念讲解

什么是 SCC？

强连通分量（Strongly Connected Component）是有向图中的极大强连通子图。

强连通

图中任意两点互相可达。

Tarjan 算法

核心思想

用 DFS 遍历图，维护：

  • dfn[u]：DFS 序
  • low[u]：能回溯到的最小 dfn

代码

12345678910111213141516171819202122232425262728293031const int N = 100005;
vector<int> graph[N];
int dfn[N], low[N], timestamp;
int stack[N], top;
bool inStack[N];
int scc[N], sccCnt;

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stack[++top] = u;
    inStack[u] = true;
    
    for (int v : graph[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inStack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    
    if (dfn[u] == low[u]) {
        sccCnt++;
        while (true) {
            int v = stack[top--];
            inStack[v] = false;
            scc[v] = sccCnt;
            if (v == u) break;
        }
    }
}

时间复杂度：O(n+m)O(n + m)

缩点

将每个 SCC 缩成一个点，构建新图。

12345678vector<int> newGraph[N];
for (int u = 1; u <= n; u++) {
    for (int v : graph[u]) {
        if (scc[u] != scc[v]) {
            newGraph[scc[u]].push_back(scc[v]);
        }
    }
}

考点分析

初赛考查方式

  1. 程序阅读： Tarjan 算法
  2. 编程题： SCC 应用

常见考点

  • Tarjan 算法
  • 缩点
  • DAG 相关问题

例题精讲

例题 1：SCC

题目： 求有向图的 SCC 数量。

解答：

使用 Tarjan 算法，统计 sccCnt。

练习题

  1. Tarjan 算法的核心思想是什么？
查看答案

Tarjan 算法的核心思想：

  1. DFS 遍历：用 DFS 遍历图
  2. 维护 dfn 和 low：
    • dfn[u]：DFS 序（访问时间）
    • low[u]：能回溯到的最小 dfn
  3. 判断 SCC：当 dfn[u] == low[u] 时，栈中从 u 到栈顶的点形成一个 SCC
  1. low 数组的含义是什么？
查看答案

low[u] 表示从 u 出发，通过 DFS 树上的边和反向边，能到达的最小 dfn 值。

  • low[u] = min(dfn[u], low[v], dfn[w])
  • v 是 u 的子节点
  • w 是 u 通过反向边能到达的节点
  1. 缩点的作用是什么？
查看答案

缩点的作用：

  1. 简化图：将每个 SCC 缩成一个点
  2. 得到 DAG：缩点后的图是无环的
  3. 便于处理：很多问题在 DAG 上更容易解决

易错点

⚠️ 注意：

  1. dfn[u] == low[u] 时形成 SCC
  2. 要用栈维护当前路径
  3. 缩点后是 DAG
  4. 时间复杂度 O(n + m)