Graph Theory37 sections · 1633 units
Open in Course

Tarjan's Algorithm - Steps

(Discovery and low-link)

Tarjan's algorithm maintains a stack of nodes in the current DFS path and tracks two arrays: disc[v]: Discovery time when node vv was first visited. low[v]: Minimum of disc[v], low[u] for all children uu, and disc[w] for all back edges vwv \to w where ww is on the stack.

When you finish processing node vv, check if low[v] = disc[v]. If yes, vv is the root of an SCC. Pop all nodes from stack down to and including vv. Assign them all the same component ID.