tarjan算法求解强连通分量

强连通分量是有向图中的概念。

在有向图中，若任意两个顶点都是连通的，那么就是强连通图，非强连通图中的强连通子图称为强连通分量。

可以用tarjan算法求解，任选一个节点作为dfs树的根节点，注意到对于节点u，若子树中的任意节点无回边到节点u的祖先（但是回到u），则子树以及u节点为一个强连通分量，也就是能通过u访问u子树的任意一个节点，但是没有任意一个节点可以返回u节点。当然该子树。

对于图1这种情况，存在从v到u的回边，那么必然在u。v构成的子图中任意节点都能回到u。

图2这种情况的话，x没有一条回到其祖先节点的回边，所以x自己构成一个强连通分量，然后剩下来的u a v构成一个强连通分量

使用low[u]表示节点u以及u的子节点回边到的祖先节点。dfsn[u]表示节点u的dfs序号。初始low[u]=dfsn[u]。如果u的子树访问完成后没有更新low[u],那么可以肯定没有回边到节点u的祖先节点。如果有节点回边到节点u，那么连同u的子树构成一个连通分量。

#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
const int MAXN=10;
struct Edge{
	int to,next;
	Edge(){}
	Edge(int a,int b):to(a),next(b){}
};
int node[MAXN],cnt,dfsn[MAXN],low[MAXN],c;
bool vis[MAXN];
Edge edge[MAXN*2];
stack<int> st;
bool inStack[MAXN];
void addEdge(int from,int to){
	edge[cnt].to=to;
	edge[cnt].next=node[from];
	node[from]=cnt++;
}
void tarjan(int from){
	vis[from]=true;
	low[from]=dfsn[from]=c++;
	inStack[from]=true;
	st.push(from);
	for(int i=node[from];i+1;i=edge[i].next){
		int to=edge[i].to;
		if(!vis[to]){
			tarjan(to);
			low[from]=min(low[from],low[to]);
		}else if(inStack[to]&&dfsn[to]<low[from]){
			low[from]=dfsn[to];
		}//存在回边到u的祖先
	}
	if(dfsn[from]==low[from]){//如果u的子节点有回到u祖先的回边，那么都不会相等
		int x;
		do{
			x=st.top();
			st.pop();
			inStack[x]=false;
			printf("%d ",x);
		}while(x!=from);
		printf("\n");
	}
}
int main(){
	freopen("./in.txt","r",stdin);
	int n,m,u,v;
	while(scanf("%d%d",&n,&m)!=EOF){
		memset(vis,false,sizeof(vis));
		memset(dfsn,-1,sizeof(dfsn));
		memset(low,-1,sizeof(-1));
		memset(node,-1,sizeof(node));
		memset(inStack,false,sizeof(inStack));
		while(!st.empty()){
			st.pop();
		}
		c=cnt=0;
		for(int i=0;i<m;i++){
			scanf("%d%d",&u,&v);
			addEdge(u,v);
		}
		tarjan(0);
	}
	return 0;
}

in.txt

5 6
0 1
1 2
2 3
2 4
3 1
4 1