强连通分量
对于一张有向图，对于图中任意两个节点\(x,y\)，\(x\)能到\(y\)，\(y\)也能到\(x\)，则称其为强连通图。有向图的极大联通子图被称为强连通分量，简记为SCC(Strongly Connected Component)。
有时候，我们需要将一张有向图分成几个强连通分量，这时候可以基于Tarjian设计一个算法。
Tarjian求强连通分量
按照Tarjiand的惯例，我们需要对整个图进行一次dfs，将图的搜索树求出，设\(dfn_x\)为\(x\)节点最先遍历到的时间戳。
对于一个节点\(x\)来说，如果有一条边连接了它与它搜索树中的祖先\(fa_x\)（不仅是父亲），说明这个点可以与树上\(fa_x\)到\(x\)的路径组成环，而显然地一个环就是一个强连通子图，有助于我们寻找强连通分量。同理，如果有一点\(z\)，它非\(x\)的祖先，但是它存在路径可以到达\(fa_x\)，那连接\(x\)与\(z\)的边也很重要。
Tarjian维护了一个栈，栈中保存了\(x\)节点的祖先\(fa_x\)，与已经访问过，并且存在一条路径到达\(x\)祖先的点。
接下来为了寻找到这些边，我们需要引入追溯值\(low_x\)。追溯值定义为满足以下条件的节点的最小时间戳：
1.该点在栈中。
2.存在一条从以\(x\)为跟的子树内出发指向\(x\)的有向边。
\(low_x\)的计算过程如下：
1.当节点\(x\)第一次访问时，将\(x\)入栈，并初始化\(low_x=dfn_x\).
2.遍历从\(x\)出发的每条边\((x,y)\):
(1).如果\(y\)未被访问，则\(y\)为\(x\)的子树内节点，它的追溯值可以更新\(low_x\)，所以访问\(y\)，回溯后令\(low_x=min(low_x,low_y)\)。
(2).若\(y\)被访问并且在栈内，则说明\(x\)可以到达这个节点后在回到自己，根据定义可以使\(low_x=min(low_x,dfn_y)\)。
下面我们来看一看如何分割强连通分量：
判定法则很简单：\(low_x=dfn_x\)，则此时栈中从\(x\)到栈顶的所有节点构成一个强连通分量。
如果\(low_x=dfn_x\)，那么说明\(x\)的字数内节点不能到达比\(x\)更早的节点再回到\(x\)（指时间戳更小），所以能形成的最大的强连通分量最大只包含了\(x\)。
以上便是\(Tarjian\)求强连通分量的主要流程。
实现
我们可以设\(ins_x=1\)表示\(x\)此刻是否在栈中，只在遍历边\((x,y)\)时\(y\)被访问过且\(ins_y=1\)时才将\(low_x\)更新为\(min(low_x,dfn_y)\)，代表\(x\)可以去到\(y\)在回来。
接下来是tarjian代码：
int dfn[maxn],low[maxn],num;
int sta[maxn],top;
int ins[maxn],cou[maxn],cnt
void tarjian(int now) {
dfn[now]=low[now]=++num;
sta[++top]=now; ins[now]=1;
for(int i=head[now];i;i=nex[i]) {
int st=to[i];
if(!dfn[st]) {
tarjian(st);
low[now]=min(low[now],low[st]);
}
else if(ins[st]) low[now]=min(low[now],dfn[st]);
}
if(dfn[now]==low[now]) {
int x; cnt++;
do {
x=sta[top--];
ins[x]=0;
cou[x]=cnt;
} while(x!=now);
}
}