Kosaraju
Kosaraju 算法学习笔记(求强连通分量)
写起来简单无比,不比 Tarjan 香? 方法 按照[1...n]的顺序在反图(边方向相反)上dfs一遍,出栈时将节点存入数组q[1...n]中 按照q[n...1]的顺序在原图上dfs一遍,每次遍历就是一个新的强联通分量 为什么是正确的? 核心在于封死连通分量往外走的路。 如果原图u-->v有一条 ......
强连通分量 - Kosaraju Algorithm
推荐在唯一官方原文阅读,但本文不是转载,是多平台发布。 Kosaraju算法(aka Kosaraju-Sharir算法)是一个求强连通分量的算法。其时间复杂度为$O(n+m)$(邻接表)或$O(m^2)$(邻接矩阵)。 该算法相比Tarjan算法要更简单一些。(个人观点) 本算法的基础是反图(也被 ......