强连通分量类

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

基于Graph类

Tarjan算法

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

Kosaraju算法

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

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

缩点

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

代码

Small_feed 评论 (0)