tarjan真的不是一种算法。

前言

tarjan是一个计算机科学家，以LCA、强连通分量等算法闻名。所以tarjan发明的算法统称tarjan算法。

强连通分量(strongly connected components)

在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量。

Slove

1. 对整张图进行dfs，用一个栈维护dfs到的所有点，再记录一下每个点是否在栈里。
2. 每个点维护两个信息：dfn表示dfs到这个点的顺序，low表示这个点能沿着非树边回到的dfn最小的点的dfn。
3. 一开始令low[u]=dfn[u]，并将u压入栈。
4. 到点u时，枚举出边(u,v)，如果没有访问到，就继续dfs点v，然后 low[u]=min(low[u],low[v])。
5. 否则，如果v当前在栈里，就令low[u]=min(low[u],dfn[v])。
6. 当u的出边枚举完时，如果low[u]=dfn[u]，就说明找到了一个强连通分量，弹栈直到弹出点u为止，这些点构成一个强连通分量。

Code

void tanjan(int s){
	dfn[s]=low[s]=++sum;
	st.push(s);  //stack<int> st
	vis[s]=true;  //是否入栈
	for(int i=first[s];i!=-1;i=next[i]){  //邻接表
		if(!dfn[to[i]]){  //to[i]-v
			tanjan(to[i]);
			low[s]=min(low[s],low[to[i]]);
		}
		else if(vis[to[i]]) low[s]=min(low[s],dfn[to[i]]);
	}
	if(dfn[s]==low[s]){
		int cur;
		cnt++;  //强连通分量编号
		do{
			cur=st.top();
			fis[cur]=cnt;
			vis[cur]=false;
			st.pop();
		}while(cur!=s);
	}
}

相关题目

P2341 [HAOI2006]受欢迎的牛|【模板】强连通分量 //其实这题原先不是模板
P2746 [USACO5.3]校园网Network of Schools

此外

蒟蒻并不会证明此解的正确性。