浅谈 Kosaraju
linhanmo
·
·
算法·理论
https://www.cnblogs.com/linhanmo/articles/19974910/kosaraju
前言
我们求强连通分量时会发现 Tarjan 太长了，其实有一个好写的算法 Kosaraju。
强连通分量
一个图是强连通的当且仅当一个图的任意两个节点都能互相到达。
强连通分量指一个图里极大的（不能在扩张的）强连通子图。
Kosaraju 算法
算法流程
两次 dfs：
-
选一个未访问过的（不保证连通）的点作为起点，求出后序遍历。直到都被访问过。
-
对于反图，从后序遍历标号最大且未访问过的的顶点作为起点开始 dfs，遍历到的就是强连通分量。直到都被访问过。
正确性证明
必要性
对于第二次 DFS 的起点记为 T，访问到的记为 S。
原图 S 可达 T：
$\therefore$ 原图 $S$ 可达 $T$。
##### 原图 $T$ 可达 $S$：
$\because T$ 后序遍历标号比 $S$ 大：
::::success[$T$ 在 DFS 树上是 $S$ 的祖先]{open}
显然 $T$ 可达 $S$。
::::
::::error[$T$ 和 $S$ 在不同的子树且 $S$ 的子树先访问到]{open}
$\because T$ 反图能到达 $S$：
$\therefore$ 原图 $S$ 可达 $T$；
又 $\because S$ 的子树先遍历到：
$\therefore S$ 比 $T$ 不超过 $S,T$ 的 LCA 的最靠近根节点的祖先先遍历到；
$\therefore$ DFS 树上是 $S$ 是 $T$ 的祖先，矛盾！
故不可能存在这种情况。
::::
#### 充分性
反证法。
假设在反图上存在一点 $S$ 和 $T$ 属于同一个强连通分量但 $S$ 并没有被 $T$ 遍历到。
::::error[$T$ 尚未被标记强连通分量且 $S$ 错过了 $T$]{open}
$\because$ 原图 $S$ 可达 $T$：
$\therefore$ 反图 $T$ 可达 $S$；
又 $\because$ $T$ 尚未被标记强连通分量；
$\therefore S$ 必然能标记 $T$。
故不存在这种情况。
::::
::::error[在 $S$ 遍历到 $T$ 之前已经被 $P$ 遍历到了]{open}
$\because T$ 被 $P$ 遍历到了：
$\therefore P,T$ 属于同一个强连通分量；
又 $\because S,T$ 属于同一个强连通分量；
$\therefore P,S$ 属于同意个强连通分量；
又 $\because P$ 的后序遍历标号比 $S$ 大；
$\therefore S$ 被 $P$ 标记，与 $S$ 仍然可以遍历矛盾。
故不存在这种情况。
::::
### 应用
#### 缩点
将整个强连通分量里的点压缩成一个点。
#### [2-SAT](https://www.luogu.com.cn/problem/solution/P4782)
Tarjan 找环改为 Kosaraju 找环即可。
#### bitset 优化
发现最耗时的于当前节点 $u$，找出所有尚未访问且与 $u$ 有边相连的节点。
假如把邻接矩阵和访问情况都压成 bitset，这一步可以用与运算和 ```_Find_first``` 优化到 $O(\frac{n}{w})$。
总时间复杂度为 $O(\frac{n^2}{w})$，适用于可以用特殊方式生成边且 $m$ 接近 $n^2$ 的场景。
### 例题
#### [P2863](https://www.luogu.com.cn/problem/P2863)
板子套用即可。
```cpp lines=9-23 line-numbers
#include <stack>
#include <vector>
#include <bitset>
#include <stdio.h>
constexpr int N = 10010;
int n, m, cnt, scc[N], sz[N], t;
std::bitset<N> v;
std::vector<int> e[N], re[N]; std::stack<int> s;
void dfs(int a) {
v.set(a);
for (int b : e[a]) if (!v[b]) dfs(b);
return s.push(a);
}
void rdfs(int a) {
scc[a] = cnt, ++sz[cnt];
for (int b : re[a]) if (scc[b] == 0) rdfs(b);
return;
}
inline void kosaraju(void) {
for (int i = 1; i <= n; ++i) if (!v[i]) dfs(i);
for (; !s.empty(); s.pop()) if (scc[s.top()] == 0) ++cnt, rdfs(s.top());
return;
}
int main(void) {
scanf("%d %d", &n, &m);
for (int a, b, i = m; i--;) scanf("%d %d", &a, &b), e[a].emplace_back(b), re[b].emplace_back(a);
kosaraju();
int ans = 0;
for (int i = 1; i <= cnt; ++i) if (sz[i] > 1) ++ans;
printf("%d", ans);
return 0;
}
```
#### [P2341](https://www.luogu.com.cn/problem/P2341)
显然同一个强连通分量里的奶牛互相受欢迎。
那么假如一个强连通分量的出度 $>0$ 那么它必然没有入度（否则就不极大了）。
所以，只有**唯一的**一个强连通分量里的奶牛是明星。
假如有多个强连通分量出度 $=0$，那么就没有明星。
```cpp lines=28-37 line-numbers
#include <stack>
#include <vector>
#include <bitset>
#include <stdio.h>
constexpr int N = 10001;
int n, m, cnt, scc[N], sz[N], t;
std::vector<int> e[N], re[N];
std::bitset<N> v, d;
std::stack<int> s;
void dfs(int a) {
v.set(a);
for (int b : e[a]) if (!v[b]) dfs(b);
return s.push(a);
}
void rdfs(int a) {
scc[a] = cnt, ++sz[cnt];
for (int b : re[a]) if (scc[b] == 0) rdfs(b);
return;
}
inline void kosaraju(void) {
for (int i = 1; i <= n; ++i) if (!v[i]) dfs(i);
for (; !s.empty(); s.pop()) if (scc[s.top()] == 0) ++cnt, rdfs(s.top());
return;
}
int main(void) {
scanf("%d %d", &n, &m);
for (int a, b, i = m; i--;) scanf("%d %d", &a, &b), e[a].emplace_back(b), re[b].emplace_back(a);
kosaraju();
for (int a = 1; a <= n; ++a) for (int b : e[a]) {
if (d[scc[a]]) break;
if (scc[a] != scc[b]) d.set(scc[a]);
}
for (int i = 1; i <= cnt; ++i)
if (!d[i]) {
if (t) return putchar(48), 0;
t = sz[i];
}
printf("%d", t);
return 0;
}
```
## 后记
虽然 Korsaraju 好写，但是 Tarjan 功能多。
所以 Tarjan 还是好好学！
- update on 2026.5.25：添加 2-SAT 和 bitset 优化。