强连通分量（Tarjan）

1 从「互相可达」说起

有向图里，两点之间的关系不是对称的： $u$ 能到 $v$ ，不代表 $v$ 能到 $u$ 。把「互相都能到」的点聚成一类，就得到了这张图最粗的一层结构。

定义强连通

在有向图 $G=(V,E)$ 中，若 $u$ 与 $v$ 互相可达（ $u\rightsquigarrow v$ 且 $v\rightsquigarrow u$ ），称 $u,v$ 强连通。若 $G$ 中任意两点都强连通，称 $G$ 是一个强连通图。

定义强连通分量

非强连通的有向图中，极大的强连通子图称为强连通分量（strongly connected component，SCC）。「极大」指点集不能再加进任何一个点而保持强连通。每个点恰好属于一个强连通分量。

「每个点恰好属于一个」这句话值得停一下：它说明求 SCC 等价于给每个点染一个颜色，同色点两两互相可达，异色点至少有一个方向走不通。把一张图按颜色收缩（每个分量当成一个点），得到的图里再没有环——这就是下文「缩点」的由来。

查看 DOT 源码

// 两个强连通分量：{1,2,3} 与 {4,5,6}，虚线是跨分量的边
digraph G {
    rankdir=LR;
    nodesep=0.35;
    ranksep=0.55;
    node [shape=circle, fixedsize=true, width=0.5, fontname="Noto Serif SC", fontsize=14];
    edge [fontname="Noto Serif SC", fontsize=12];
    1 -> 2;
    2 -> 3;
    3 -> 1;
    3 -> 4;
    4 -> 5;
    5 -> 6;
    6 -> 4;
    3 -> 5 [style=dashed];
}

2 朴素做法，以及它为什么慢

要判断 $u,v$ 是否强连通，最直接的办法是从 $u$ 出发做一次 DFS 记下可达集合 $R(u)$ ，再在反图上从 $u$ 出发做一次 DFS 记下能到达 $u$ 的集合 $R'(u)$ 。 $R(u)\cap R'(u)$ 就是 $u$ 所在的强连通分量。

每个点都做一次，代价是 $O\bigl(n(n+m)\bigr)$ 。 $n=10^5$ 时完全不可行。

更好的方法是 Kosaraju（正图、反图各跑一次 DFS，按出栈顺序挑起点）和 Tarjan（一次 DFS 用栈和两个数组直接划出分量），都是 $O(n+m)$ 。Kosaraju 更好想、好写；Tarjan 只要一次 DFS，常数更小，还能顺手处理割点、边双连通分量。下面讲 Tarjan。

3 DFS 树上，一个分量连成一片

Tarjan 的全部内容都建立在 DFS 树的性质上，先把这条性质说清楚，否则后面的 low 会变成背公式。

定理同一个分量的点在同一棵 DFS 树里

若 $u,v$ 强连通，则在任意一次 DFS 中，它们一定落在同一棵 DFS 树上；并且其中被先访问的那个点，是后者的祖先。

证明只需要一句：设 $u$ 先被访问。此时 $v$ 还没被访问，而 $u\rightsquigarrow v$ ，DFS 会从 $u$ 一路搜下去，遇到 $v$ 时把它接进 $u$ 的子树。 $\square$

由此，一个分量在 DFS 树上表现为「以某个点 $r$ 为根、连成一片的区域」， $r$ 就是分量里 dfn 最小的点，本文称它为这个分量的根。

但请注意： $r$ 的子树里可能有别的分量的点。 上图从 $1$ 出发 DFS，得到的树是 $1\to2\to3\to4\to5\to6$ ，而 $3$ 的子树是 $\{3,4,5,6\}$ ，其中 $4,5,6$ 属于另一个分量。所以说「分量是 DFS 树的一棵子树」是不准确的；准确的说法是「分量在子树内部，是它的一段连续部分」。怎么把这一段从子树里挑出来，正是栈要解决的问题。

算法Tarjan 的一句话

DFS 时把点按访问顺序压栈；一个点 $u$ 能回到的最早编号等于自己的访问编号时，它就是所在分量的根，此时栈顶到 $u$ 之间的点正好是这个分量。

4 dfn、low 与栈

维护三样东西：

dfn[u]： $u$ 被首次访问的序号，从 $1$ 开始，DFS 每进入一个新点就加一。
low[u]：从 $u$ 出发、只沿 DFS 树往下走再借助至多一条非树边，能到达的仍在栈中的点的最小 dfn。直观说，它是 $u$ 的子树所能「退回」的最早位置。
一个栈：按访问顺序压入，尚未确定分量的点都留在里面。

遍历 $u$ 的每条出边 $u\to v$ ，按 $v$ 的状态分三种情况：

边的类型	判断条件	处理
树枝边（ $v$ 未访问）	`vis[v] == 0`	先递归 `dfsscc(v)`，回来再 `low[u] = min(low[u], low[v])`
返祖边（ $v$ 在栈中）	`vis[v] && in_sta[v]`	`low[u] = min(low[u], dfn[v])`
指向已出栈的点（横叉边）	`vis[v] && !in_sta[v]`	忽略： $v$ 属于更早完成的分量

两类更新为什么不一样？树枝边下去的是自己子树里的点，子树的信息已经算全了，所以取 low[v]；返祖边指向的是祖先，祖先的 low 可能因为别的原因被拉得更早，但这里只需要「 $u$ 能碰到祖先 $v$ 」这一件事，所以取 dfn[v]。

说明讨论：返祖边能不能写 low[u] = min(low[u], low[v])

不少文章这样写，也常常能过题。但成立需要额外论证「 $v$ 还在栈中」能推出什么，而这个前提在不同图上的含义并不一样；dfn[v] 的语义是封闭的——只用到「 $v$ 是祖先」这一条，不依赖别处的计算顺序。模板里保留 dfn[v] 的写法。

退出 $u$ 时做最后一次判断：

\text{若 } \text{low}[u]=\text{dfn}[u] \quad\Longrightarrow\quad u \text{ 是某个分量的根}

引理栈里「更早」的点一定是祖先

设正在处理 $u$ 。若某条边 $x\to y$ 满足： $x$ 在 $u$ 的子树中、 $y$ 仍在栈中、且 $\text{dfn}[y]<\text{dfn}[u]$ ，则 $y$ 一定是 $u$ 的祖先。

证明： $y$ 的 dfn 比 $u$ 小，说明 $y$ 先于 $u$ 被访问。若 $y$ 不是 $u$ 的祖先，它就在别的子树里，那个子树在 $u$ 开始之前就已经搜完；一个分量的根退栈时分量内的点全部弹出，所以早已搜完的 $y$ 不可能还留在栈里。 $\square$

这条引理说清了 Tarjan 的底气：low 只会被「栈里更早的点」拉低，而栈里更早的点一定是祖先，祖先与当前点之间天生有返回路径，于是互相可达成立。

定理根的判据

low[u] = dfn[u] 当且仅当 $u$ 是所在分量的根（分量中 dfn 最小的点）。

两个方向分别论证。

方向一：low[u] < dfn[u]，则 $u$ 不是根。 由引理，栈里有 $u$ 的祖先 $y$ 被 $u$ 的子树碰到，于是 $y\rightsquigarrow u$ （树边）且 $u\rightsquigarrow y$ （经过那条边），两点强连通。而 dfn[y] < dfn[u]，所以 $u$ 不是分量里第一个被访问的点。

方向二： $u$ 不是根，则 low[u] < dfn[u]。 设所在分量的根为 $r$ （dfn[r] < dfn[u]），取一条从 $u$ 到 $r$ 的路径 $u=x_0\to x_1\to\cdots\to x_k=r$ ，令 $x_i$ 是路径上第一个 dfn 小于 dfn[u] 的点，则 $x_{i-1}$ 还在 $u$ 的子树里。

关键一步： $x_i$ 与 $u$ 属于同一个分量。因为 $x_i\rightsquigarrow r$ （路径余下的部分）、 $r\rightsquigarrow u$ （同分量）、 $u\rightsquigarrow x_i$ （前半段路径），三段拼成环。既然 $u$ 还没出栈，同分量的 $x_i$ 也没有出栈，处理 $x_{i-1}$ 时它就在栈里。于是 $\text{low}[x_{i-1}] \le \text{dfn}[x_i] < \text{dfn}[u]$ ，而 low[u] 只会被 $u$ 的子树拉得更小，矛盾于 low[u] = dfn[u]。

判据成立时弹出栈：从栈顶一直弹到 $u$ （含），弹出的点染同一个颜色。栈里在 $u$ 上面的点恰好都是本分量的点——不属于本分量的点，在各自分量的根退栈时早就弹掉了。

5 走一遍例子

输入格式：第一行 $n,m$ ，接下来 $m$ 行有向边 $u\to v$ 。用上面那张图：

DFS 过程中状态变化如下（栈写成「底 → 顶」）：

事件	`dfn`	`low`	栈	说明
进入 1	1	1	`1`
进入 2	2	2	`1 2`	$1\to2$ 是树枝边
进入 3	3	3	`1 2 3`	$2\to3$ 是树枝边
走 $3\to1$	3	1	`1 2 3`	1 在栈中，`low[3] = min(3, dfn[1]) = 1`
进入 4	4	4	`1 2 3 4`	走 $3\to4$
进入 5	5	5	`1 2 3 4 5`
进入 6	6	6	`1 2 3 4 5 6`
走 $6\to4$	6	4	`1 2 3 4 5 6`	4 在栈中，`low[6] = 4`
退出 6	6	4	`1 2 3 4 5 6`	`low ≠ dfn`，不是根，不出栈
退出 5	5	4	`1 2 3 4 5 6`	`low[5] = min(5, low[6]) = 4`
退出 4	4	4	`1 2 3 4 5 6`	`dfn = low`，是根，弹出 6 5 4 → 分量①
回到 3	3	1	`1 2 3`	`low[3] = min(1, low[4]) = 1`，不受影响
走 $3\to5$	3	1	`1 2 3`	5 已出栈，属于别的分量，忽略
退出 3	3	1	`1 2 3`	`low ≠ dfn`，不是根
退出 2	2	1	`1 2 3`	不是根
退出 1	1	1	`1`	`dfn = low`，是根，弹出 3 2 1 → 分量②

结果： $\{4,5,6\}$ 是第一个分量（最早完成）， $\{1,2,3\}$ 是第二个。注意分量编号是按出栈时刻给的，与点的编号无关，更不是拓扑序。

这张表里三种边都出现了，可以逐行对着看：

$1\to2$ 、 $2\to3$ 、 $4\to5$ 、 $5\to6$ 是树枝边；
$3\to1$ 、 $6\to4$ 是返祖边（环就是靠它们被发现的）；
$3\to5$ 是横叉边，而且 $5$ 已经出栈，所以它对 low[3] 毫无影响——如果这里错误地写成「访问过就更新」， $5$ 所在分量的信息就会污染 $\{1,2,3\}$ 的 low。

6 代码模板

模板把图存成链式前向星（linkList），栈自己用数组维护（mystack），递归函数是 dfsscc。

//Author by [Rainboy](https://github.com/rainboylvx)
//date: 2024-12-5 10:28
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
const int maxe = 1e6+5;

int n,m;
int dfn[maxn],low[maxn]; // dfn: 访问序号  low: 能退回的最早序号
bool vis[maxn];          // 是否访问过
bool in_sta[maxn];       // 是否在栈内
int _time;               // 访问计时器
int color_idx;           // 强连通分量个数
int color[maxn];         // color[i]: 点 i 属于哪个强连通分量

//图的存储结构,linkList
struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    //遍历点u 周围点
    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w); //u v w
    }

    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    void add2(int u,int v,int w=0){
        add(u,v,w);
        add(v,u,w);
    }
    //下标访问
    edge& operator[](int i){ return e[i]; }
    //返回head[u]
    int operator()(int u){ return h[u]; }
} e;

template<typename T = int,int siz = maxn>
struct mystack{
    T sta[siz+5];
    int head = 0;

    void clear() { head = 0;}

    void push(T a) { sta[head++] = a;}

    void pop(){head--;}

    T top() { return sta[head-1];}

    bool empty() { return head == 0;}

    int size() { return head;}
};
mystack sta; //栈


//读取数据
void init(){
    std::cin >> n >> m;
    for(int i = 1;i <= m ;++i ) // i: 1->m
    {
        int u,v;
        std::cin >> u >> v;
        e.add(u,v);
    }
}

void dfsscc(int u) {
    vis[u] = 1;
    dfn[u] = low[u] = ++_time;
    sta.push(u); //入栈
    in_sta[u] = 1;
    for(int i = e(u);i != -1 ;i= e[i].next)
    {
        int v = e[i].v;
        if( vis[v] == 0)
        {
            dfsscc(v);

            //孩子能通过返祖边到的最早祖先,更新自己
            low[u] = min(low[u],low[v]);
        }
        else if( in_sta[v] )
        {
            // 一条返祖边
            low[u] = min(low[u],dfn[v]);
        }
    }
    //退出点u时，进行检查
    if( low[u] == dfn[u]) { // 回不到更早点
        //设定点u为根的子树上的点强连通的编号
        int t;
        color_idx++;
        do {
            t = sta.top();
            sta.pop();
            in_sta[t] = 0;
            color[t] = color_idx;
        }while( t != u);
    }
}



int main () {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // 关闭io同步
    init();
    for(int i =1;i<=n;i++)
    {
        if( vis[i] == 0) //如果没有访问过
            dfsscc(i);
    }
    //输出每个点的强连通编号
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        cout << "node " << i << ": " << color[i] << endl;
    }
    return 0;
}

几处要点：

e.add(u,v) 是头插，所以 e(u) 遍历出边的顺序与输入顺序相反。这不会影响结果（分量与遍历顺序无关），但会让你看到的 dfn 顺序与「按输入顺序想象」的不一样。
vis[u] 与 in_sta[u] 是两件事：前者表示「进过一次 DFS」，后者表示「还没出栈，即分量未定」。第三种情况（访问过但已出栈）就靠 in_sta 排除。
退栈时先 in_sta[t]=0 再染色，两者顺序无所谓，但都要在 t != u 的循环体里执行。

注意多连通块：循环里不要写死起点

1
2
3

for (int i = 1; i <= n; i++)
    if (vis[i] == 0)
        dfsscc(i);   // 不能写成 dfsscc(1)

写成 dfsscc(1) 时，只有 $1$ 能到达的点会被染色，其余点的 color 全是 $0$ 。这个错误在单连通块的样例上完全看不出来，一交就挂。

注意递归深度

dfsscc 的递归层数最多是 $n$ 。 $n=10^6$ 时会先撞上系统栈（默认 $8$ MB 左右），表现为段错误而不是 TLE。三个办法：把 maxn 调到实际数据范围、用 ulimit -s 或 -Wl,--stack 放大栈、或者改成手写栈迭代版。

复杂度：每个点只入栈、出栈一次，每条边只看一次，时间 $O(n+m)$ ；dfn/low/color/vis/in_sta 与栈都是 $O(n)$ ，链式前向星 $O(n+m)$ 。

7 缩点：把分量当成一个点

既然分量内部任意两点互相可达，把它们压成一个点不丢失任何关于可达性的信息。这就是缩点，也是 Tarjan 在题目里最常被用到的形态。

定理缩点后是 DAG

把每个强连通分量缩成一个点、分量之间的边照原样保留，得到的图一定是有向无环图。

若缩点后有环 $C_1\to C_2\to\cdots\to C_k\to C_1$ ，则这些分量两两互相可达，它们本该是同一个分量，与「极大」矛盾。 $\square$

有了 DAG，就能接上拓扑排序上的一切：入度为 $0$ 的起点、最长路、计数、可达性。典型写法是在 Tarjan 之后扫一遍所有边统计入度：

int in_deg[maxn] = {0};
for (int u = 1; u <= n; u++) {
    for (int i = e(u); i != -1; i = e[i].next) {
        int v = e[i].v;
        if (color[u] != color[v]) // 跨分量的边，才计入度
            in_deg[color[v]]++;
    }
}

说明重边与自环

同一条跨分量边重复出现时，in_deg 会被重复累加——如果题目只问「有多少个分量的入度为 $0$ 」，这不影响答案；如果问「入度为 $1$ 的分量」，就必须先去重（或用一个 bool 数组按分量对去重）。分量内部的边（包括自环）在缩点后消失，color[u] == color[v] 直接跳过即可。