强连通分量类

orz hhw posted @ 2018年7月17日 11:38 in 算法学习 with tags 算法学习 模板 Tarjan 联通分量 , 87 阅读

基于Graph类

Tarjan算法

基于DFS序和low数组,求得每个强连通分量

Kosaraju算法

先对原图进行一遍DFS,按DFS序的顺序在反图中DFS,每次DFS到的点属于同一个强连通分量。

时间复杂度$O(m)$,如果边数较多,可以用bitset优化到$O(\frac{n^2}{32})$

缩点

将同一个强连通分量的点缩在一个点中,不在同一个强连通分量的点连边,得到一个拓扑图。

代码