浅谈 Kosaraju
Planetary_system
·
·
算法·理论
0x00 前言
声明：本文中文字，图片都是作者本人亲自编辑。如使用请经过作者的允许。
图论是 OI 的一大板块，其中有一个重要算法 Tarjan。或许你第一次学习 Tarjan 就是求强连通分量，也或许你还不会求强连通分量，本文将介绍另一种较冷门算法——Kosaraju 来求强连通分量。
0x01 强连通分量&缩点
在将如何求强连通分量之前，我们先介绍一下强连通分量。
强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通。
强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。
这是 oi-wiki 给出的定义，似乎比较晦涩。关于强连通分量，我的理解就是一个点的集合，集合内的点满足互相可达，加入任何一个其他点都将不再满足。
强连通分量有一个很重要的性质：把有向图中所有强连通分量缩成一个顶点，就得到了一个有向无环图（Directed Acyclic Graph，DAG），而这个过程被称为 缩点。
如图，每个红线框中的点就是一个强连通分量，而缩点后变成了一个有向无环图。这里很好理解，如果有环在环上转一圈就双向可达了，那就是同一个强连通分量了。
正因为有这个性质以及有向无环图许多优秀的性质，很多时候只要转换成 DAG 题目就很简单了，于是在很多题目中我们就有了求强连通分量的必要性。
0x02 算法原理
Kosaraju 算法：也称为 Kosaraju-Sharir 算法，最早在 1978 年由 S. Rao Kosaraju 在一篇未发表的论文上提出，但 Micha Sharir 最早发表了它。
首先有这样一个基本事实：一个有向图 G，把 G 的所有的边反向，建立反图 G'，反图 G' 不会改变原图 G 的强连通性。也就是说，原来是 SCC 的子图，反图中仍是 SCC；原来不是 SCC 的子图，反图中仍不是 SCC。
这个基本事实很好理解。u,v 强连通等价与存在路径 u\to v 与路径 v\to u，那反图中分别变成路径 v\to u 与 u\to v，仍然强连通。反之，若原图不存在 u\to v，反图就不存在 v\to u，不强连通，不存在 v\to u 同理。
基于此，我们可以建立正图与反图，分别使用 dfs 遍历一次：
不难发现这个做法的时间复杂度是线性的。
0x03 模拟过程
仍以上图作例。
第一次遍历我们从 1 开始。
$6$ 能到 $10$，$10$ 入栈能到 $11$，$11$ 入栈能到 $12$，$12$ 入栈能到 $13$。$13$ 入栈无处可去，出栈。
所有点已经被遍历一遍，以入栈顺序倒序依次出栈。
得到后序遍历为：$9,8,7,13,12,11,10,6,5,4,3,2,1$。
第二次遍历，需要遍历反图，反图如图。
按上文说的，后序遍历最后一个是 $1$，$1$ 入栈无处可去，出栈，第一个 SCC 为 $\{1\}$。
此时最后一个是 $2$，一样无处可去，第二个 SCC 为 $\{2\}$。
$3$ 能到 $5$，$5$ 能到 $4$。第三个 SCC 为 $\{3,4,5\}$。
$6$ 能到 $9$，依次遍历 $6\to9\to8\to7$，这四个点组成第四个 SCC。
同理，还有三个 SCC 分别为 $\{10\}$，$\{11,12\}$，$\{13\}$。
结果正确。你也可以试试其他遍历顺序，来验证这个算法的正确性。
## 0x04 感性理解
猜你想问：为什么这样两遍 dfs 就能找出所有强连通分量了？~~（让你问你就问！）~~
我们已经获得了一个后序遍历，我们从最后面的一个元素 $u$ 开始遍历，到达的每个节点 $v$ 都满足后序遍历在 $u$ 之前且 $G$ 中存在 $v\to u$ 的路径。
直觉上，后序遍历中，原图中能走到很多节点的入栈较靠前的节点排在前面，在最后的点是能去到的点很少的点。那么很少的点 $u$ 都能到 $v$ 了，我们可以认为 $v$ 可以到 $u$。那么也就能大致理解为什么 $u$ 和 $v$ 在同一个 SCC 了。
事实上这不是 Kosaraju 正确的真正原因，主要是在于以逆后序遍历顺序遍历反图的巧妙性。上述只是本人的感性理解方式，大佬们可以当看个乐子。
## 0x05 严谨证明
其实能理解会写就够了，处于完整考虑还是给出证明。
观察得到：在 $G$ 上进行 dfs 得到的后序遍历中，对于任意两个节点 $u$ 和 $v$，如果存在从 $u$ 到 $v$ 的路径，那么 $u$ 的出栈时间晚于 $v$ 的出栈时间。换句话说，$v$ 会在后序序列中出现在 $u$ 的前面。
考虑后序遍历中的最后一个元素 $v_1$，在 $G$ 中，$v_1$ 是出栈时间最晚的节点，假设 $v_1$ 属于强连通分量 $C_1$，在 $G^{SCC}$ 中，$C_1$ 必须是源分量（没有入边的分量）。因为如果存在其他分量 $C'$ 指向 $C_1$，那么 $C'$ 中必有节点 $u$ 存在到 $v_1$ 的路径，而 $u$ 的出栈时间应晚于 $v_1$，与 $v_1$ 是出栈时间最晚的节点，矛盾。在反图 $G'$ 中，源分量变成汇分量（没有出边的分量），因此从 $v_1$ 开始在 $G'$ 上 dfs，只能访问到 $C_1$ 内的节点。
归纳一下：假设前 $k$ 次 dfs 已经正确找出了 $k$ 个强连通分量，从图中移除这 $k$ 个分量后，考虑剩余图中逆后序最靠前的未访问节点 $v_{k+1}$。
设 $v_{k+1}$ 属于强连通分量 $C_{k+1}$，在剩余子图中，$C_{k+1}$ 是源分量。因为如果存在剩余的其他分量 $C'$ 指向 $C_{k+1}$，那么 $C'$ 中必有节点 $u$ 存在到 $v_{k+1}$ 的路径，$u$ 的出栈时间应晚于 $v_{k+1}$，与 $v_{k+1}$ 是剩余图中逆后序最靠前的节点矛盾。在反图 $G'$ 的剩余部分中，$C_{k+1}$ 变成汇分量，因此从 $v_{k+1}$ 开始在 $G'$ 的剩余部分上 dfs，只能访问到 $C_{k+1}$ 内的节点。
## 0x06 代码实现
这是最轻松的部分，个人喜欢 Kosaraju 的一大原因就是代码十分简单！只需照着上述思路模拟即可，可以说没有代码难度。下面给出本人封装后的丑陋代码，不喜轻喷。
```cpp
namespace Kosaraju{
int n,c[N],tot;
bool vis[N];
stack<int>st;
vector<int>e[N],_e[N],g[N];
void dfs1(int u){
vis[u]=1;
for(int v:e[u])if(!vis[v])dfs1(v);
st.push(u);
}
void dfs2(int u,int o){
c[u]=o;
//此处处理点权（将u的信息合并到o）
for(int v:_e[u])
if(!c[v])dfs2(v,o);
}
void Rebuild(){
for(int u=1;u<=n;u++)for(int v:e[u])
if(c[u]^c[v])g[c[u]].push_back(c[v]);
}
void Kos(){
for(int u=1;u<=n;u++)for(int v:e[u])
_e[v].push_back(u);
for(int i=1;i<=n;i++)
if(!vis[i])dfs1(i);
while(!st.empty()){
if(!c[st.top()])dfs2(st.top(),++tot);
st.pop();
}
Rebuild();
}
}
```
也可以使用一个 `map` 或者 `bitset` 记录边有没有加过避免重边。
Kosaraju 算法时间复杂度 $O(n+m)$，与 Tarjan 相同，稠密图等价于 $O(n^2)$。
## 0x07 优化
一般情况下，Tarjan 比 Kosaraju 有更小的常数，泛用性也更强。但稠密图可以轻松地卡掉 Tarjan,原因是 Kosaraju 可以使用 `bitset` 优化。
上文刚说完稠密图中 Kosaraju 和 Tarjan 的复杂度达到 $O(n^2)$，但 Kosaraju 可以优化为 $O(\frac{n^2}{\omega})$。你只需要把邻接表改成邻接矩阵即可，`_Find_first` 函数可以直接找下一个 $1$。
```cpp
namespace Kosaraju{
int n,c[N],tot;
stack<int>st;
vector<int>G[N],g[N];
bitset<N>vis,e[N],_e[N];
#define nxt _Find_first
void dfs1(int u){
vis[u]=1;
bitset<N>x=e[u]&(~vis);
for(int v=x.nxt();v<=n;v=x.nxt(v))
dfs1(v);
st.push(u);
}
void dfs2(int u,int o){
c[u]=o,vis[u]=1;
bitset<N>x=_e[u]&(~vis);
for(int v=x.nxt();v<=n;v=x.nxt(v))
dfs2(v,o);
}
void Rebuild(){
for(int u=1;u<=n;u++)
for(int v=e[u].nxt();v<=n;v=e[u].nxt(v))
if(c[u]!=c[v])g[c[u]].push_back(c[v]);
}
void Kos(){
for(int u=1;u<=n;u++)
for(int v:G[u])
e[u][v]=_e[v][u]=1;
for(int i=1;i<=n;i++)
if(!vis[i])dfs1(i);
vis.reset();
while(!st.empty()){
if(!c[st.top()])dfs2(st.top(),++tot);
st.pop();
}
Rebuild();
}
}
```
同样，你也可以再开一个 `bitset` 来保证生成的 DAG 中没用重边。
## 0x08 2-sat
既然 Kosaraju 可以求 SCC，那么显然，我们也可以用他来解决经典的 **2-sat** 问题。那么在解决之前，我们先来看看什么叫 2-sat。
你可以先阅读 [2-sat 模板题](https://www.luogu.com.cn/problem/P4782) 的题面。
我们发现题目给出的限制是 $p \vee q$ 的形式，那么 $\neg p \wedge \neg q$ 的情况不合法，故有 $\neg p$ 则 $q$，$\neg q$ 则 $p$。这种一个条件推出另一个条件的形式，可以抽象为一条有向边。我们将每个命题于其否定拆开（两个命题互为矛盾命题），于是就可以建出一个有向图。
这时我们发现，如果两个点同属于一个 SCC，则这两个点对应的命题互为充要条件，即一个 SCC 具有相同的真伪性。显然存在一组矛盾命题在同一个 SCC 内与此问题无解是充要条件。
对应在我们的实现中就是：将命题抽象成点（$i$ 表示第 $i$ 个命题，$i+n$ 表示其否定），将限制抽象为有向边，缩点后，无解即 $\exists i,c_i=c_{i+n}$。
接下来的问题是，有解的情况下，我们该如何构造出一组合法的答案？事实上我们只需要按逆拓扑序构造，Kosaraju 算法保证了 SCC 的编号顺序是拓扑序的逆序，所以对于 $i$ 和 $i+n$ 取 $c$ 更小的使其为真即可。
不难证明这是正确的。首先如果存在边 $u+n \to v$，根据建图方式必然有 $v+n \to u$。假设存在不满足的限制 $u\vee v$，即 $u$ 和 $v$ 都为假，有 $c_{u+n}<c_u$ 和 $c_{v+n}<c_v$；而由于有向边的存在又有 $c_{v+n}>c_u$ 和 $c_{u+n}>c_v$。二者显然是矛盾的，所以这种构造方式不会产生冲突。
在做题过程中需要注意的是，你的 $i$ 和 $i+n$ 分别对应的是题目中的什么状态，以及题目的约束条件究竟应该转换成什么哪两个点之间的有向边。例如在[本题](https://www.luogu.com.cn/problem/P4782)中，我选择将 $i$ 对应 $1$，$i+n$ 对应 $0$，所以最后输出的是 $c_i>c_{i+n}$。
在求解 2-sat 问题时，个人认为 Kosaraju 对比 Tarjan 具有显著的优势。一方面是过程直接保证逆拓扑序，另一方面就是代码实现没有任何细节。
## 0x09 缺陷
虽然上文提及了 Kosaraju 的诸多优点，但也不得不承认，更大的常数和更窄的使用范围，使得实用性是远不如 Tarjan 的。面对割点，桥，点双，边双之类的经典问题 Kosaraju 就没有一战之力了。
## 0x0A 总结
我说完了。