浅谈 Kosaraju
linhanmo
·
·
算法·理论
https://www.cnblogs.com/linhanmo/articles/19974910/kosaraju
前言
我们求强连通分量时会发现 Tarjan 太长了，其实有一个好写的算法 Kosaraju。
强连通分量
一个图是强连通的当且仅当一个图的任意两个节点都能互相到达。
强连通分量指一个图里极大的（不能在扩张的）强连通子图。
Kosaraju 算法
算法流程
两次 dfs：
-
选一个未访问过的（不保证连通）的点作为起点，求出后序遍历。直到都被访问过。
-
对于反图，从后序遍历标号最大且未访问过的的顶点作为起点开始 dfs，遍历到的就是强连通分量。直到都被访问过。
代码见例题 P2863。
正确性证明
必要性
对于第二次 DFS 的起点记为 T，访问到的记为 S。
原图 S 可达 T：
$\therefore$ 原图 $S$ 可达 $T$。
##### 原图 $T$ 可达 $S$：
$\because T$ 后序遍历标号比 $S$ 大：
::::success[$T$ 在 DFS 树上是 $S$ 的祖先]
显然 $T$ 可达 $S$。
::::
::::error[$T$ 和 $S$ 在不同的子树且 $S$ 的子树先访问到]
$\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$]
$\because$ 原图 $S$ 可达 $T$：
$\therefore$ 反图 $T$ 可达 $S$；
又 $\because$ $T$ 尚未被标记强连通分量；
$\therefore S$ 必然能标记 $T$。
故不存在这种情况。
::::
::::error[在 $S$ 遍历到 $T$ 之前已经被 $P$ 遍历到了]
$\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$ 的场景。
:::success[核心代码]
```cpp
void dfsG(int u) {
nvs[u] = false;
while ((tmp = nvs & G[u]).any()) dfsG(tmp._Find_first());
vec[++sz] = u;
}
void dfsH(int u) {
nvs[u] = false;
while ((tmp = nvs & H[u]).any()) dfsH(tmp._Find_first());
++sz;
}
```
:::
### 例题
#### [P2863](https://www.luogu.com.cn/problem/P2863)
:::success[板子套用即可]
```cpp
#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$，那么就没有明星。
:::success[代码]
```cpp
#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;
}
```
:::
#### [QOJ 12805](https://qoj.ac/problem/12805/)
求互相可达的点的对数。
显然就是求强连通分量，每个强连通分量对答案的贡献为 $\frac{S(S-1)}{2}$。
bitset 优化即可。
:::success[板子套用]
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define For(i, st, ed) for (register int i = (st); i <= (ed); ++i)
template<typename type> inline void read(type &x) {
int f = 0, ch; while (ch = getchar(), ch < 48 || ch > 57) f ^= ch == 45;
x = 0; do x = x * 10 + (ch ^ 48); while (ch = getchar(), ch > 47 && ch < 58); f ? x = -x : 0;
}
constexpr int N = 260;
int n, m, q, ans, sz, vec[N]; char e[N];
bitset<N> G[N], H[N], nvs, tmp;
void dfsG(int u) {
nvs[u] = false;
while ((tmp = nvs & G[u]).any()) dfsG(tmp._Find_first());
vec[++sz] = u;
}
void dfsH(int u) {
nvs[u] = false;
while ((tmp = nvs & H[u]).any()) dfsH(tmp._Find_first());
++sz;
}
int kosaraju() {
sz = ans = 0, nvs.set();
For(i, 1, n) nvs[i] ? dfsG(i) : void();
nvs.set();
for (register int i = n; i >= 1; --i)
if (nvs[vec[i]]) sz = 0, dfsH(vec[i]), ans += sz * (sz - 1) / 2;
return ans;
}
signed main() {
read(n), read(q);
For(i, 1, n) { scanf("%s", e + 1); For(j, 1, n) G[i][j] = H[j][i] = e[j] ^ '0'; }
For(Q, 1, q) {
read(m);
For(M, 1, m) { int u, v; read(u), read(v), G[u].flip(v), H[v].flip(u); }
printf("%d\n", kosaraju());
}
return 0;
}
```
:::
### [P1653](https://www.luogu.com.cn/problem/P1653)
连高度从大到小的单向边，kosaraju 缩点。
统计入度出度，求出无入边的块数和无出边的块数即为答案。
### [P1407](https://www.luogu.com.cn/problem/P1407)
将初始的情侣看成一个点，kosaraju 找强连通分量。
若大小等于一，安全，否则不安全。
## 优缺点
优点：
- 代码短，好记好写。
- bitset 优化。
缺点：
- 除 bitset 外功能被 tarjan 偏序。
- 不考。
## 后记
字数统计：5587 字符。
- update on 2026.5.25：添加 2-SAT 和 bitset 优化。
- update on 2026.8.10：添加 bitset 优化的代码与例题、更多例题、优缺点。