tarjan实现强联通分量

• 图论

定义:强联通分量

在有向图中,一个强联通分量就代表这个图中某个区域任意点可以到达任意点。以此类推,两点直接或间接联通就叫做强联通。

Tarjan实现

很简单,Dfs序先标一个号。如果点u的儿子可以达到点u甚至点u的父亲,爷爷..祖先,那么这一块都是可以互相联通的,如图:

如此类推,tarjan就出来了,如果不懂或者需要标称,参见:Blog。