SCC算法求强连通分量简单讲解证明及实现

强连通分量

连通分量要求任意两点可达，而强连通分量要求任意两点互相可达，即必须存在a->b且b->a的路径

强连通分量问题就是求解一个图中所有的强连通分量集合。

SCC算法简介

SCC算法在《算法导论》中有介绍到，SCC算法基于dfs，通过两次dfs可以求出图中所有的连通分量，是快速的方法。

在了解SCC算法之前先介绍两个概念

两个概念

dfs结束时间

规定一种【结束时间】，表示dfs退栈时候的时间，我们可以用两个数字表示dfs进栈，退栈的时间。如下图所示，左边的数字是dfs开始时间，右边的数字是dfs结束时间。
在这里插入图片描述
dfs结束时间可以表示拓扑排序的序列，即结束时间大的，拓扑排序排在结束时间小的节点前面，本质上表示退栈的先后，即访问顺序

转置图

即有向图的出边改为入边
在这里插入图片描述

SCC算法伪代码描述

对原图dfs并且将节点按照【结束时间】从大到小排序形成序列seq[]
按照seq[]序列里面的节点顺序 对【转置图】dfs 搜到的每一个连通分支就是一个强连通分量

？当我打出❓的时候，

这也太抽象了吧，所以下面给出证明

SCC算法正确性证明

证明过程需要一些引理的帮助，下面介绍几个引理

引理1：

假设有两个强连通分量c1和c2，并且存在从c1到c2的边，那么一定不存在从c2到c1的边。

在这里插入图片描述
证明很简单，如果存在边从c2到c1，那么c1c2就是同一个强连通分量，而不是两个强连通分量了。

引理2：

如果c1到c2有边，那么强连通分支【c1中最晚结束节点】的结束时间，一定晚于【c2中最晚结束节点】的时间。

在正向图中，c1的结束时间一定晚于c2，那么有：
在转置图中，c2的结束时间一定晚于c1

原因也很简单，因为c1一定先于c2被访问，毕竟要到达c2必先经过c1，转置图相当于边全反过来，所以存在边从c2到c1，而由引理1，不存在边从c1到c2了，同理可得c2的结束时间晚于c1。

SCC证明

假设原图中有强连通分量c1，在转置图上按照【原图中dfs结束时间从大到小】顺序dfs，一定能够找到c1内的所有点。并且不会找到其他强连通分支内

不错找

先来证明在反向图上对c1中的点dfs，不会找到其他分支内的点，即不错找

反证法：假设原图有强连通分支c1和c2，而我们在转置图中对c1内的点dfs，能够找到c2内的点，这表明转置图中有边c1到c2，也就是说原图中有边c2到c1，那么说明c2所有点的结束时间晚于c1中的所有点，那么在转置图的dfs中，c2的点一定先于c1的点被dfs到，所有c1的点永远到不了c2的点，即不会【错找】
在这里插入图片描述

不漏找

这个好理解，假设存在x->y表示x到y有路径

强连通分量中，存在a->b和b->a，那么将边全部反向变成转置图之后

a->b(原) 变为 b->a(新)
b->a(原) 变为 a->b(新)

仍然存在存在 a->b和b->a，是强连通，不漏找

代码实现

ps：其实第一次dfs，退栈之后的节点装到一个栈里面。dfs结束之后，按照顺序弹出节点，就是结束时间从晚到早的排序序列

#include <bits/stdc++.h>

using namespace std;

int n, e, ans=0;
vector<vector<int>> adj;
vector<vector<int>> adj_T;	// 转置图 
vector<int> vis;
vector<int> seq;	// 存节点 下标越大 结束时间越晚

// dfs原图 
void dfs(int x)
{
	vis[x] = 1;
	for(int i=0; i<adj[x].size(); i++)
		if(vis[adj[x][i]]==0) dfs(adj[x][i]);
	seq.push_back(x);
}

// dfs转置图 
void dfs_T(int x)
{
	vis[x] = 1;
	for(int i=0; i<adj_T[x].size(); i++)
		if(vis[adj_T[x][i]]==0) dfs_T(adj_T[x][i]);
}

int main()
{ 	
	cin>>n>>e;
	adj.resize(n); adj_T.resize(n); vis.resize(n);
	for(int i=0; i<e; i++)
	{
		int st, ed; cin>>st>>ed;
		adj[st].push_back(ed);
		adj_T[ed].push_back(st);
	}
	
	// dfs原图 
	for(int i=0; i<n; i++) 
		if(vis[i]==0) dfs(i);
	// 重置vis 
	for(int i=0; i<n; i++) vis[i]=0;
	// 按照seq的顺序dfs转置图 
	for(int i=n-1; i>=0; i--) 
		if(vis[seq[i]]==0) dfs_T(seq[i]),++ans; 
	cout<<"强连通分量个数: "<<ans<<endl;
	
	return 0;
}

/*
6 8
0 1
0 4
1 2
2 0
2 1
3 2
4 5
5 4
*/

秒客网