More Formal Statement

Input is a graph G=(V,E) (possibly with cycles) of n nodes and m directed edges.

Output is a set of components C, and a mapping $c:V\rightarrow C$ from nodes to components of interreachability, and edges D between components denoting one-way reachability.

Properties:

• If there is some path from u to v and from v to u, then c(u) = c(v).
• If u and v are in different components and there is an edge from u to v, then $(c(u), c(v)) \in D$.
• The component graph G'=(C,D) is a DAG.

How would you do it? Let's try an example.