浅谈 Kosaraju

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

开始。

1

入栈能到

2

，

2

入栈能到

3

，

3

入栈能到

4

，

4

能到

5

，

5

入栈能到

6

，

6

入栈能到

7

，

7

入栈能到

8

，

8

入栈能到

9

。

9

入栈无处可去，出栈，

8

出栈，

7

出栈。

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 模板题的题面。

我们发现题目给出的限制是

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

分别对应的是题目中的什么状态，以及题目的约束条件究竟应该转换成什么哪两个点之间的有向边。例如在本题中，我选择将

i

对应

1

，

i+n

对应

0

，所以最后输出的是

c_i>c_{i+n}

。

在求解 2-sat 问题时，个人认为 Kosaraju 对比 Tarjan 具有显著的优势。一方面是过程直接保证逆拓扑序，另一方面就是代码实现没有任何细节。

0x09 缺陷

虽然上文提及了 Kosaraju 的诸多优点，但也不得不承认，更大的常数和更窄的使用范围，使得实用性是远不如 Tarjan 的。面对割点，桥，点双，边双之类的经典问题 Kosaraju 就没有一战之力了。

0x0A 总结

我说完了。

文章操作

0x00 前言

0x01 强连通分量&缩点

0x02 算法原理

0x03 模拟过程

0x04 感性理解

0x05 严谨证明

0x06 代码实现

0x07 优化

0x08 2-sat

0x09 缺陷

0x0A 总结

相关推荐

评论

浅谈 Kosaraju