Graph Theory37 sections · 1633 units
Open in Course

SCC Templates

(Code references)

Save templates for both Kosaraju and Tarjan SCC algorithms. Kosaraju template: Two DFS functions (one for finish times, one for SCCs), a stack for finish order, transpose graph, and two visited arrays. Tarjan template: One DFS function with discdisc, lowlow, on_stackon\_stack arrays, and a stack for the current DFS path.

Check low[v] = disc[v] to detect SCC roots. Both templates are about 3030-4040 lines of code. Practice writing them from memory until you can implement either algorithm in 55 minutes.