Definition. Let \(reach(v)\) denote the set of vertices which vertex \(v\) can reach, and let \(coreach(v)\) denote the set of vertices which can reach \(v\).

Definition. A connected component in a directed graph \(G\) is a set of vertices of the form \(reach(w)\cap coreach(w)\) for some \(w\in V\). In other words it is a “maximal” set of vertices \(W\subseteq V\) with the following property: - For any \(w,v\in V\) there is a path from \(w\) to \(v\) and a path from \(v\) to \(w\).

So what I mean by maximal is, if you think about it a bit “\(x,y\) are both reachable from each other” forms an equivalence relation and then the equivalence classes are the strongly connected compoennts (SCCs).

Proposition. SCC graph is a DAG

ok, but how can we compute SCC?

Proposition. Let \(rev(G)\) denote the graph obtained by flipping all the edges in \(G\). Then a source compoenent in \(G\) is a sink component in \(rev(G)\) and vice versa.

  1. Compute a post-order of \(rev(G)\).
  2. Use this to identify a source component in \(rev(G)\) i.e. a sink component in \(G\)
  3. DFS in the sink component and remove it.
  4. cross out stuff from the postorder, and then find a new sink component.
  5. repeat and stuff

wow, it;s linear time algorithm!