关于 Kosaraju 算法的简单证明

别搁那儿用那难理解、代码还长的 Tarjan 算法求强连通分量了。Kosaraju 是神！

介绍：

今天抱着复习 Tarjan 的想法打开了录播课，结果老师抛开其不谈，跟我们讲起了 Kosaraju 算法。
结果完全被这种思想简练，代码实现通俗易懂的算法给深深震撼了。

其核心思想是：无向图的强连通分量好求，只要是一次 dfs 能到的点，那都是强连通的。 那假如我能按照某种顺序遍历有向图，我也能利用类似简单的方法求出有向图的强连通分量。

对于一个图 G，求其所有强连通分量只要 4 步：

对于该图 $G$ 的 1~n 号节点，依次利用 dfs 找出其 dfs 搜索树的 逆后序遍历 ;
将该图每条边方向取逆，构造其反向图 $G^T$
对着 $G$ 按着上述遍历的顶点顺序，依次进行 dfs 得到其 dfs 搜索森林。（无向图的思想）
此时，森林里的每棵树所组成的所有节点，即组成一个强连通分量。

证明：

这种想法过于易于实现，导致了众博客介绍该算法时忽略了 最基础的证明，笔者在此给出一份严谨性不强但通俗的证明方法。

基本术语：

dfs 搜索树：一棵 按照某特定顺序 深度遍历各顶点所得到的搜索树。
$G^T$ ：指图 $G$ 的反向图。

命题确立：

$u$ 与 $v$ 强连通，等价于：

在图 $G$ 中存在一条路径使得 u 到 v，且在图 $G$ 中存在另一条路径使得 v 到 u；
在 $G^T$ 的 dfs 搜索树中，他们有共同的祖先（即在一棵树上）；

其中第二点是我们根据 Kosaraju 算法得到的已知条件。

证明过程：

不妨假设 x 为 u 于 $G^T$ 搜索树上的根节点。则在图 $G^T$ 中必存在一条路径使得 x 到 u (1)；
由于 $G^T$ 是 $G$ 的反向图，则在图 $G$ 中必存在一条路径使得 u 到 x；（证了一半）
假设在图 $G$ 中不存在路径使得 x 到 u，即 dfs 时会先搜索到 u 再搜索 x，那么此时 x 先结束深搜；由（1）可知，x 的后序遍历在 u 之后，即 u 节点先结束深搜，x 再结束深搜。两者矛盾。

综上，得到 u 与 x 强连通；相似地，v 也与 x 强连通。即 u 与 v 强连通。

证明过程并非十分严谨，望读者予以指正。

附录：洛谷 P3387

#include <bits/stdc++.h>
#define cle(x) memset(x,0,sizeof(x))
#define ok cout<<'!'<<endl
#define inf 2147483647
#define ll long long
#define fir first
#define sec second
#define pr pair<int,int>
using namespace std;

int read()
{   int x=0,f=0; char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return f?-x:x;
}

const int maxn = 20001, maxm = 100100;
int n, m, a[maxn], u[maxm], v[maxm]; //初始信息
int A[maxn], s[maxn], id[maxn], in[maxn], f[maxn], cnt;  
//s[i] 用栈来模拟倒序, id[i]新图节点编号, in[i]新图的入度;
bool vis[maxn];
vector<int> g[maxn], g1[maxn], G[maxn];

void dfs1(int x)
{
    vis[x] = 1;
    for (auto u:g[x]) if (!vis[u]) dfs1(u);
    s[++s[0]] = x;  return;
}

void dfs2(int x)
{
    id[x] = cnt, A[cnt] += a[x];
    for (auto u:g1[x]) if (!id[u]) dfs2(u);
    return;
}

int topo()
{
    queue<int> q;  int ans = 0;
    for (int i=1;i<=cnt;i++) if (!in[i]) f[i]=A[i],q.push(i);
    while (!q.empty()) {
        int k = q.front(); q.pop();
        for (auto u:G[k]) {
            f[u] = max(f[u],f[k]+A[u]), in[u]--;
            if (!in[u]) q.push(u);
        }
    }
    for (int i=1;i<=cnt;i++) ans = max(ans, f[i]);
    return ans;
}

int main()
{
    cin >> n >> m;
    for (int i=1;i<=n;i++) cin >> a[i];
    for (int i=1;i<=m;i++) 
        cin >> u[i] >> v[i], g[ u[i] ].push_back( v[i] ),g1[ v[i] ].push_back( u[i] );
    for (int i=1;i<=n;i++) if (!vis[i]) dfs1(i); 
    for (int i=s[0];i>=1;i--) if (!id[s[i]]) cnt++, dfs2(s[i]);
    for (int i=1;i<=m;i++) {
        int x = id[u[i]], y = id[v[i]];
        if (x != y) in[y]++, G[x].push_back(y);
    }
    cout << topo() << '\n';
    return 0;
}

参考资料：

https://gtl.csa.iisc.ac.in/dsa/node171.html