Graph/kosaraju_scc library

🔁 Kosaraju's Algorithm (Strongly Connected Components)

Computes SCCs in a directed graph using two DFS passes:

  1. DFS on original graph to compute finishing times (order)
  2. DFS on reversed graph in decreasing finish-time order to extract SCCs
  • Time complexity: O(V + E)
  • Space complexity: O(V)

Functions

kosarajuSCC<T>(Map<T, List<T>> graph) → List<Set<T>>