如何深入浅出的理解Kosaraju

前言

今天想起来Kosaraju，网上关于这个算法的介绍比较少。（毕竟Tarjan太强了）。但是Tarjan和Kosaraju的复杂度都是 $O(V+E)$ 的，Kosaraju的常数要大一点。（网上有的博客说kosaraju会卡爆栈，个人感觉不会，退化成链的情况Tarjan和Kosaraju都会一搜到底）。

那为什么Kosaraju常数大还要学它呢，用Tarjan不好吗？

因为它简单、好理解啊。毕竟Tarjan难理解是出了名的。

正题

一些必要概念

网上介绍各种概念五花八门，不够深入浅出。首先要理解这几个概念：

前序序列（从一点开始遍历，结点进入的序列）
后序序列（从一点开始遍历，结点退出的序列）
逆后序序列（就是后序序列的逆序，没什么高深的意思，~~所以百度搜不到~~）
图 $G$
反图 $G'$ （将图 $G$ 的各个边反过来重新建图，出边改入边）
强连通分量SCC（移步百度）

求前序序列和后序序列的代码（如果上面不理解，看看代码就懂了）

int n, dcnt, fcnt, c[N], d[N], vis[N], f[N];
vector<int> G[N];
void dfs(int x) {
    d[x] = ++dcnt;
    vis[x] = 1;
    for (auto y : G[x]) {
        if (!vis[y]) dfs(y);
    }
    v[x].n = ++fcnt;
}
void solve() {
    dcnt = fcnt = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) dfs(i);
    }
}

Kosaraju如和实现

两遍DFS：

第一遍，求出图G的逆后序序列。
第二遍，根据逆后序序列，在反图 $G'$ 上进行DFS，每次能dfs点就在一个强连通分量里。

代码：

int n, c[N], dfn[N], vis[N], dcnt, scnt;
vector<int> G1[N], G2[N];  // G1 原图，G2 反向图
void dfs1(int x) {         // 求后序序列
    vis[x] = 1;
    for (auto y : G1[x]) {
        if (!vis[y]) dfs1(y);
    }
    dfn[++dcnt] = x;
}
void dfs2(int x) {
    c[x] = scnt;
    for (auto y : G2[x]) {
        if (!c[y]) dfs2(y);
    }
}
void kosaraju() {
    dcnt = scnt = 0;
    memset(c, 0, sizeof(c));
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) dfs1(i);
    }
    // 反过来遍历dfn就是逆后序序列
    for (int i = n; i >= 1; i--) {
        if (!c[dfn[i]]) ++scnt, dfs2(dfs[i]);
    }
}