如果两个顶点可以相互通达,则称两个顶点强连通。如果有向图G的每两个顶点都强连通,称G是一个强连通图。有向图的极大强连通子图,称为强连通分量。
那么给定一张图,该如何求出这张图的连通分量呢(同时也可以算出强连通分量)。
Tarjan算法是基于DFS的算法,每个强连通分量为搜索树中的一棵子树。搜索时,把当前搜索树中未处理的节点加入一个栈,回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
vector<int> g[10005];
vector<vector<int> > ans;
int vis[10005],dfn[10005],low[10005];
//dfn[i]表示i点第一次被搜索到的时间戳,low[i]表示这个点和它连通的点的最小时间戳
//vis[i]表示这个点是否在栈中
stack<int> s;
int cnt = 0;
bool cmp(vector<int> a,vector<int> b)
{
return a.size() > b.size();
}
void tarjan(int x)
{
dfn[x] = low[x] = ++cnt;
s.push(x);
vis[x] = 1;
for (int i = 0; i < g[x].size(); i++)
{
int t = g[x][i];
if( !dfn[t] ) //如果该点没有被搜过
{
tarjan(t);
low[x] = min(low[x],low[t]); //只有一种情况会更新:t这个点与x之前的点构成连通,那么t也一定与x连通
//否则low[t]一定会比low[x]大
}else if( vis[t] ) //如果该点已经在栈中了,说明该点与x连通
{
low[x] = min(low[x],low[t]); //那么我们更新x的时间戳即可
}
}
if( dfn[x] == low[x] ) //在搜索了与x相邻的所有点后,如果dfn[x] == low[x],那么这一定是一个连通块
{ //如果dfn[x] != low[x],那么说明这个点一定与之前被访问的点是连通的,这时我们不选择输出答案。
//而是在最小的那个时间戳再输出
vector<int> res; //当前连通分量的结果
res.push_back(x);
vis[x] = 0;
while( s.top() != x ) //如果栈顶元素不等于x的话,说明这个点与x一定是连通的。
{
res.push_back(s.top());
vis[s.top()] = 0;
s.pop();
}
s.pop();
ans.push_back(res);
}
}
int main()
{
int n,m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int x,y;
cin >> x >> y;
g[x].push_back(y);
}
for (int i = 1; i <= n; i++)
{
if( !dfn[i] ) tarjan(i);
}
sort(ans.begin(),ans.end(),cmp); //按照每个连通分量的长度排序,最大的那个就是强连通分量了
for (int i = 0; i < ans.size(); i++)
{
for(int j = 0; j < ans[i].size(); j++)
{
cout << ans[i][j] << " ";
}
cout << endl;
}
return 0;
}
复杂度为O(V+E)