本地源文件：docs/graph__scc.md

强连通分量

简介

在阅读下列内容之前，请务必了解图论相关概念中的基础部分．

强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通．

强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图．

这里要介绍的是如何来求强连通分量．

Tarjan 算法

引入

Robert E. Tarjan（罗伯特·塔扬，1948~），生于美国加州波莫纳，计算机科学家．

Tarjan 发明了很多算法和数据结构．不少他发明的算法都以他的名字命名，以至于有时会让人混淆几种不同的算法．比如求各种连通分量的 Tarjan 算法，求 LCA（Lowest Common Ancestor，最近公共祖先）的 Tarjan 算法．并查集、Splay、Toptree 也是 Tarjan 发明的．

我们这里要介绍的是在有向图中求强连通分量的 Tarjan 算法．

DFS 生成树

在介绍该算法之前，先来了解 DFS 生成树 ，我们以下面的有向图为例：

DFS 生成树

在有向图 𝐺G 上运行 DFS 算法时，由于边具有方向性，从单个结点出发可能无法访问到图中的全部结点．因此，我们需要遍历整个顶点集：对每个尚未被访问的结点，都重新发起一次 DFS．在每一次从某个起始结点出发并完成的 DFS 过程中，其所经过的树边（见下文）会构成一棵树，称为 DFS 生成树 ．当所有结点都被访问后，得到的 DFS 生成树的全体构成了该有向图的 DFS 生成森林 ．

需要注意的是，生成树（以及生成森林）的具体结构，以及下文中的边分类，都依赖于 DFS 的起始结点选择和邻接点的访问顺序．

有向图 𝐺G 的边可分为四类：

树边（tree edge）：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边．所有相邻的树边组成 DFS 生成树．
反祖边（back edge）：也称回边，示意图中以红色边表示（即 7 →17→1），指在搜索过程中，从某个结点指向其祖先结点的非树边．
前向边（forward edge）：示意图中以绿色边表示（即 3 →63→6），指在搜索过程中，从某个结点指向其子树中后代结点的非树边．
横叉边（cross edge）：示意图中以蓝色边表示（即 9 →79→7），指在搜索过程中，从某个结点指向非祖先、非后代且已访问的结点的边，即不属于上述三类的边．

我们考虑 DFS 生成树与强连通分量之间的关系．

如果结点 𝑢u 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 𝑢u 为根的子树中．结点 𝑢u 被称为这个强连通分量的根．

反证法：假设有个结点 𝑣v 在该强连通分量中但是不在以 𝑢u 为根的子树中，那么 𝑢u 到 𝑣v 的路径中肯定有一条离开子树的边．但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点已经被访问过了，这就和 𝑣v 不在以 𝑢u 为根的子树中矛盾了．得证．

Tarjan 算法求强连通分量

Tarjan 算法基于对图进行深度优先搜索．我们视每个连通分量为搜索树中的一棵子树，在搜索过程中，维护一个栈，每次把搜索树中尚未处理的节点加入栈中．

在 Tarjan 算法中为每个结点 𝑢u 维护了以下几个变量：

𝑑𝑓𝑛𝑢dfnu：深度优先搜索遍历时结点 𝑢u 被搜索的次序．
𝑙𝑜𝑤𝑢lowu：在 𝑢u 的子树中能够回溯到的最早的已经在栈中的结点．设以 𝑢u 为根的子树为 𝑆𝑢𝑏𝑡𝑟𝑒𝑒𝑢Subtreeu．𝑙𝑜𝑤𝑢lowu 定义为以下结点的 𝑑𝑓𝑛dfn 的最小值：𝑆𝑢𝑏𝑡𝑟𝑒𝑒𝑢Subtreeu 中的结点；从 𝑆𝑢𝑏𝑡𝑟𝑒𝑒𝑢Subtreeu 通过一条不在搜索树上的边能到达的结点．

一个结点的子树内结点的 dfn 都大于该结点的 dfn．

从根开始的一条路径上的 dfn 严格递增，low 严格非降．

按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索，维护每个结点的 dfn 与 low 变量，且让搜索到的结点入栈．每当找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈．在搜索过程中，对于结点 𝑢u 和与其相邻的结点 𝑣v（𝑣v 不是 𝑢u 的父节点）考虑 3 种情况：

𝑣v 未被访问：继续对 𝑣v 进行深度搜索．在回溯过程中，用 𝑙𝑜𝑤𝑣lowv 更新 𝑙𝑜𝑤𝑢lowu．因为存在从 𝑢u 到 𝑣v 的直接路径，所以 𝑣v 能够回溯到的已经在栈中的结点，𝑢u 也一定能够回溯到．
𝑣v 被访问过，已经在栈中：根据 low 值的定义，用 𝑑𝑓𝑛𝑣dfnv 更新 𝑙𝑜𝑤𝑢lowu．
𝑣v 被访问过，已不在栈中：说明 𝑣v 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作．

将上述算法写成伪代码：

实现

---|---

对于一个连通分量图，我们很容易想到，在该连通图中有且仅有一个 𝑢u![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 使得 𝑑𝑓𝑛𝑢 =𝑙𝑜𝑤𝑢dfnu=lowu![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．该结点一定是在深度遍历的过程中，该连通分量中第一个被访问过的结点，因为它的 dfn 和 low 值最小，不会被该连通分量中的其他结点所影响．

因此，在回溯的过程中，判定 𝑑𝑓𝑛𝑢 =𝑙𝑜𝑤𝑢dfnu=lowu![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 是否成立，如果成立，则栈中 𝑢u![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 及其上方的结点构成一个 SCC．

### 实现

C++Python

---|---

---|---

时间复杂度 𝑂(𝑛 +𝑚)O(n+m)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．

### 分量标号和拓扑序的关系

Tarjan 算法在处理过程中，实际上是按照某种 **逆拓扑序** 来发现强连通分量的，这是因为算法在深度优先搜索的过程中会先访问完那些没有出边的节点，而这与拓扑排序的过程是相反的．

如果我们将图中的所有强连通分量缩成单个节点，那么在这些缩点后的节点形成的 DAG 中进行拓扑排序，得到的顺序将与 Tarjan 算法给出的强连通分量的标号顺序相反．

因此，可以说，在缩点后的 DAG 中，**强连通分量（缩点后）的标号顺序是其拓扑序的逆序** ．但要注意的是，这种说法仅在考虑了强连通分量之间的依赖关系（即从一个强连通分量到另一个强连通分量的有向边）时才成立．单个强连通分量内部的节点由于存在环，所以内部并不满足拓扑序的定义．

## Kosaraju 算法

### 引入

Kosaraju 算法最早在 1978 年由 S. Rao Kosaraju 在一篇未发表的论文上提出，但 Micha Sharir 最早发表了它．

### 过程

该算法依靠两次简单的 DFS 实现：

第一次 DFS，选取任意顶点作为起点，遍历所有未访问过的顶点，并在回溯之前给顶点编号，也就是后序遍历．

第二次 DFS，对于反向后的图，以标号最大的顶点作为起点开始 DFS．这样遍历到的顶点集合就是一个强连通分量．对于所有未访问过的结点，选取标号最大的，重复上述过程．

两次 DFS 结束后，强连通分量就找出来了，Kosaraju 算法的时间复杂度为 𝑂(𝑛 +𝑚)O(n+m)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．

### 实现

C++Python

---|---

---|---

## Garbow 算法

### 过程

Garbow 算法是 Tarjan 算法的另一种实现，Tarjan 算法是用 dfn 和 low 来计算强连通分量的根，Garbow 维护一个节点栈，并用第二个栈来确定何时从第一个栈中弹出属于同一个强连通分量的节点．从节点 𝑤w![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 开始的 DFS 过程中，当一条路径显示这组节点都属于同一个强连通分量时，只要栈顶节点的访问时间大于根节点 𝑤w![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 的访问时间，就从第二个栈中弹出这个节点，那么最后只留下根节点 𝑤w![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)．在这个过程中每一个被弹出的节点都属于同一个强连通分量．

当回溯到某一个节点 𝑤w![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7) 时，如果这个节点在第二个栈的顶部，就说明这个节点是强连通分量的起始节点，在这个节点之后搜索到的那些节点都属于同一个强连通分量，于是从第一个栈中弹出那些节点，构成强连通分量．

### 实现

C++Python

---|---

---|---

## 应用

我们可以将一张图的每个强连通分量都缩成一个点．

然后这张图会变成一个 DAG，可以进行拓扑排序以及更多其他操作．

举个简单的例子，求一条路径，可以经过重复结点，要求经过的不同结点数量最多．

## 习题

[USACO Fall/HAOI 2006 受欢迎的牛](https://loj.ac/problem/10091)

[POJ1236 Network of Schools](http://poj.org/problem?id=1236)

* * *

>  __本页面最近更新： 2026/3/27 18:45:49，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/graph/scc.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/graph/scc.md "edit.link.title")
>  __本页面贡献者：[Ir1d](https://github.com/Ir1d), [sshwy](https://github.com/sshwy), [Enter-tainer](https://github.com/Enter-tainer), [H-J-Granger](https://github.com/H-J-Granger), [StudyingFather](https://github.com/StudyingFather), [countercurrent-time](https://github.com/countercurrent-time), [NachtgeistW](https://github.com/NachtgeistW), [hsfzLZH1](https://github.com/hsfzLZH1), [ksyx](https://github.com/ksyx), [Tiphereth-A](https://github.com/Tiphereth-A), [AngelKitty](https://github.com/AngelKitty), [Anguei](https://github.com/Anguei), [CCXXXI](https://github.com/CCXXXI), [chenquanwen](https://github.com/chenquanwen), [cjsoft](https://github.com/cjsoft), [diauweb](https://github.com/diauweb), [Early0v0](https://github.com/Early0v0), [ezoixx130](https://github.com/ezoixx130), [GekkaSaori](https://github.com/GekkaSaori), [iamtwz](https://github.com/iamtwz), [Konano](https://github.com/Konano), [LovelyBuggies](https://github.com/LovelyBuggies), [Makkiy](https://github.com/Makkiy), [mgt](mailto:i@margatroid.xyz), [minghu6](https://github.com/minghu6), [ouuan](https://github.com/ouuan), [P-Y-Y](https://github.com/P-Y-Y), [PotassiumWings](https://github.com/PotassiumWings), [SamZhangQingChuan](https://github.com/SamZhangQingChuan), [ShaoChenHeng](https://github.com/ShaoChenHeng), [Suyun514](mailto:suyun514@qq.com), [Unnamed2964](https://github.com/Unnamed2964), [weiyong1024](https://github.com/weiyong1024), [Xeonacid](https://github.com/Xeonacid), [alphagocc](https://github.com/alphagocc), [Cat-shao](https://github.com/Cat-shao), [cnszlijz](https://github.com/cnszlijz), [dongzhiwei-git](https://github.com/dongzhiwei-git), [Entiesci](https://github.com/Entiesci), [F1shAndCat](https://github.com/F1shAndCat), [GavinZhengOI](https://github.com/GavinZhengOI), [Gesrua](https://github.com/Gesrua), [Great-designer](https://github.com/Great-designer), [HanwGeek](https://github.com/HanwGeek), [HeRaNO](https://github.com/HeRaNO), [ImpleLee](https://github.com/ImpleLee), [JulieSigtuna](https://github.com/JulieSigtuna), [kxccc](https://github.com/kxccc), [lychees](https://github.com/lychees), [Marcythm](https://github.com/Marcythm), [mcendu](https://github.com/mcendu), [Menci](https://github.com/Menci), [MicDZ](https://github.com/MicDZ), [mizusakuraed](https://github.com/mizusakuraed), [Peanut-Tang](https://github.com/Peanut-Tang), [Qiu-Quanzhi](https://github.com/Qiu-Quanzhi), [shawlleyw](https://github.com/shawlleyw), [shuzhouliu](https://github.com/shuzhouliu), [Siger Young](mailto:siger-young@users.noreply.github.com), [SukkaW](https://github.com/SukkaW), [Tokur233](https://github.com/Tokur233), [xiaoh1024](https://github.com/xiaoh1024), [xmb3857](https://github.com/xmb3857)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用