Categories
Algorithms

Strongly Connected Component using Tarjan’s Algorithm

Kosaraju’s vs Tarjan’s Kosaraju’s algorithm finds the Topological Sorting of the original directed graph. For this, it uses DFS. Next it reverses the graph and runs DFS on the topologically sorted vertices. So it takes two DFS though the time complexity is O(|V|+|E|). Tarjan’s algorithm, on the other hand, only uses one DFS but uses […]