Module Components.Make
Functor providing functions to compute strongly connected components of a graph.
Parameters
Signature
val scc : G.t -> int * (G.V.t -> int)
scc g
computes the strongly connected components ofg
. The result is a pair(n,f)
wheren
is the number of components. Components are numbered from0
ton-1
, andf
is a function mapping each vertex to its component number. In particular,f u = f v
if and only ifu
andv
are in the same component. Another property of the numbering is that components are numbered in a topological order: if there is an arc fromu
tov
, thenf u >= f u
Not tail-recursive. Complexity: O(V+E) The function returned has complexity O(1)