求有向图的强连通分量(tarjan算法)

2019/7/24 11:30:20 人评论 次浏览 分类:学习教程

如果两个顶点可以相互通达,则称两个顶点强连通。如果有向图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)

相关资讯

  • 那些我们不愿意承认的事

    很久没有见的老朋友,准确的说应该是很久没有见过的老师,一个比我大两岁的老师,我上初中的时候他从高中回来教我了一年。后来又回去上高中,我上高中的时候他上大学,现在我刚大学毕业他创办了公司。昨日一见依然如故,他还是热爱销售,而我却成了纯粹的技术人员。 看到他…

    2015/6/22 13:12:47

学习教程

共有访客发表了评论 网友评论

验证码: 看不清楚?

    立即查看