（点击上方公众号，可快速关注）
转自：ivy-end
http://www.ivy-end.com/archives/1001
好文投稿， 请点击 → 这里了解详情
强连通分量（Strongly Connected Components），简称SCC。
是指在给定的一张图 G=(V,E) 的一个子图 G′=(V,E) 这个子图满足对于其中的任意一对点 ⟨Vi,Vj⟩ 均存在这样两条路径⟨Vi,⋯,Vj⟩。
如果我们把强连通分量缩成一个点，这时候，原图 G 则会变成有向无环图。
图 G=(V,E) 是有向无环图当且仅当该图中没有点集合元素个数大于 1 的强连通分量。且任意一个强连通分量都至少包含一个有向环。
下面我们通过一张图片来理解一下强连通分量以及缩点：
对于统计给定的图G=(V,E)中强连通分量的个数，我们可以应用并查集在O(α(V)⋅V)时间内得到求解。
如果不仅需要统计强连通分量的个数，还要将强连通分量缩点，则需要用到今天介绍的Kosaraju Algorithm。它的具体步骤如下：
1、对原图G进行DFS并将出栈顺序进行逆序，得到的顺序就是拓扑序列。
将原图的每一条边反向，得到反图G′。
2、按照第一步生成的拓扑序列的顺序再对反图G′进行DFS染色，染成同色的就是一个强连通分量。
3、这个算法比较容易理解，也是最通用的算法。它主要是同时运用了原图G和反图G′。
该算法具有一个性质：如果我们把求出来的每个强连通分量缩成一个点，并且用求出每个强连通分量的顺序来标记收缩后的结点，那么这个顺序就是强连通分量缩点后所形成的有向无环图的拓扑序列。
#include
#include
#include
using namespace std;
const int MAX = 10240;
int N, M, nCnt = 0;
int pMap[MAX][MAX], pColor[MAX];
stack<int> S; // 储存拓扑序列
void dfs1(int x); // 原图DFS
void dfs2(int x); // 反图DFS
void Kosaraju();
int main()
{
cin >> N >> M;
memset(pMap, 0, sizeof(pMap));
for(int i = 1; i <= M; i++)
{
int s, e;
cin >> s >> e;
pMap[s][e] = 1; // 有向图
}
Kosaraju();
return 0;
}
void Kosaraju()
{
memset(pColor, 0, sizeof(pColor));
for(int i = 1; i <= N; i++) // DFS原图求出拓扑序列
{
if(!pColor[i])
{ dfs1(i); }
}
memset(pColor, 0, sizeof(pColor));
while(!S.empty()) // 按照拓扑序列DFS反图
{
int x = S.top(); S.pop();
if(!pColor[x])
{
nCnt++; // 找到一个强连通分量
dfs2(x);
}
}
cout << "The number of SCC is " << nCnt << endl;
}
void dfs1(int x)
{
pColor[x] = 1; // 染色
for(int i = 1; i <= N; i++)
{
if(pMap[x][i] == 1 && !pColor[i])
{ dfs1(i); }
}
S.push(x); // 加入拓扑序列
}
void dfs2(int x)
{
pColor[x] = nCnt; // 属于第几个强连通分量
for(int i = 1; i <= N; i++)
{
if(pMap[i][x] == 1 && !pColor[i]) // 原邻接矩阵的对称矩阵为反图
{ dfs2(i); }
}
}
觉得本文有帮助？请分享给更多人
关注「算法爱好者」，修炼编程内功
淘口令：复制以下红色内容，再打开手淘即可购买
范品社，使用￥极客T恤￥抢先预览（长按复制整段文案，打开手机淘宝即可进入活动内容）
