Kosaraju 算法学习记录

· · 个人记录

根据定义，同一个强连通分量肯定是能互相到达的，也就是说 u 能走到 v，那么 v 也能反过来走到 u

kosaraju 算法就是先一遍 dfs 记录每一个节点的访问顺序，并建立反边，然后以被访问时间由 晚 \rightarrow 早的顺序遍历每一个尚未标记的节点，设其为 s_i，对于每一个 s_i，沿着反边往回搜，所以搜到的点也就与它处于同一个强连通分量了，要把这些点标记上