Skip to main content

tarjan_scc

Function tarjan_scc 

pub fn tarjan_scc(adj: &[Vec<usize>]) -> Vec<Vec<usize>>
Expand description

Strongly-connected components of a directed graph via iterative Tarjan. Each returned Vec is the node ids of one SCC. A singleton component is a node on no cycle; a component of size ≥ 2 is a dependency cycle (tangle).

Tarjan emits components in reverse-topological order; callers that need a stable order should sort.