有向图的强连通分量
概念：在有向图中，若点a与b间存在路径，则a与b连通，若存在a到b的路径同时存在b到a的路径则成a与b强连通，若一个有向图中任意两点均强连通，则此图为强连通图，一个有向图的极大强连通子图称为强连通分量。
求强连通分量可以转化为求环路及无出度的顶点，使用DFS遍历图可以使得我们更清楚的看清环路及无出度顶点，例如：

图中有两个环，但是可以合并为一个强连通分量，所以只找环和无出度点是不完整的，因此我们可以去找极大连通子图对应子树的根，上图中为顶点1，分析一波，1号顶点的特点是从1号顶点出发的所有路径中可以追溯到的DFS序最小的顶点同样是1，且其他顶点不具备这个特点，因此引入DFN数组保存所有顶点的DFS时序，LOW数组保存所有顶点可以追溯到的最小DFS时序，则1号顶点特点为LOW=DFN，当前问题重点转化为求LOW，LOW的求解是递归的，当前顶点的LOW为其所有孩子顶点LOW的最小值，LOW初始化为DFN，因为最大就是DFN，边界条件为当前顶点无孩子或孩子又是祖先，无孩子时，LOW保持DFN不变，孩子为祖先时，因为祖先孩子的LOW依赖当前的LOW，所以此时要与祖先孩子的DFN比较取最小，找到一个满足条件的根，则输出这颗子树，不会产生干扰。

#include<iostream>
#include<vector>
#include<stack>
#include<string.h>
#define Size 101

using namespace std;

int n,m,DFS_Clock=0;
vector<int> Map[Size];
int LOW[Size],DFN[Size];
stack<int> Stack;
bool InSt[Size];

void CreateMap()
{
	int a,b;
	cin>>n>>m;
	for(int i=1;i<=n;++i) Map[i].clear();
	for(int i=1;i<=m;++i){
		cin>>a>>b;
		Map[a].push_back(b);
	}
}

int Min(int a,int b) {return a<b?a:b;}

void Tarjan(int now)
{
	LOW[now]=DFN[now]=++DFS_Clock;//建立DFS遍历时序DFN，LOW初始化为DFN 
	Stack.push(now);//当前顶点入栈 
	InSt[now]=true;//入栈标记 
	for(int i=0;i<Map[now].size();++i){
		int next=Map[now][i];//枚举now连接的所有顶点next 
		if(!DFN[next]){//如果next还没有遍历到
			Tarjan(next);//递归遍历next，以此建立LOW[next] 
			LOW[now]=Min(LOW[now],LOW[next]);//递归返回LOW[next]，以此建立LOW[now] 
		}else if(InSt[next]){//如果next遍历过了且还在栈中，递归的边界之一
			LOW[now]=Min(LOW[now],DFN[next]);
		}
	}
	if(LOW[now]==DFN[now]){//如果now为强连通分量根，输出栈中now及其之后元素，即为一个强连通分量 
		int top_elem;
		do{
			top_elem=Stack.top();
			Stack.pop();
			cout<<top_elem<<' ';
			InSt[top_elem]=false;
		}while(top_elem!=now);
		cout<<endl;
	}
}

int main()
{
	CreateMap();
	memset(DFN,0,sizeof(DFN));
	memset(InSt,false,sizeof(InSt));
	for(int i=1;i<=n;++i)
	    if(!DFN[i]) Tarjan(i);
	
	return 0;
}
/*
6 10
1 4
1 5
1 6
2 1
2 3
5 2
5 3
5 4
6 3
6 5
*/