求有向图的强连通分量（tarjan算法）

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