Computing Strongly Connected Component Proof

Proof

1. Each depth-first tree found in DFS $G^T$ is a SCC

2. Let $C$, $C^{\prime }$ be distinct SCC of $G$

3. Define max_finish(C) = max{finish_time(u) | u in C}

4. If some vertex $u\in C$ has an edge in $G$ to some $v\in C^{\prime }$ then:

5. max_finish(C) > max_finish(C')

   1. $C$ discovered earlier - will go from $C$ to $C^{\prime }$ then finish $C^{\prime }$ then back to finish $C$
   2. $C^{\prime }$ discovered earlier - $C^{\prime }$ finished without visiting $C$ because no path from $C^{\prime }$ to $C$

6. In $G^T$ if some vertex $v\in C^{\prime }$ has an edge to some $u\in C$, then max_finish(C) > max_finish(C')

7. If max_finish(C) > max_finish(C') then in $G^T$ no edge from $C$ to $C^{\prime }$

8. DFS $G^T$

   1. Start vertex $s\in C$, with largest max_finish(C) of all SCC
   2. Visit all vertices reachable from $s$
   3. $G^T$ has no edge from $C$ to another SCC $C^{\prime }$
   4. never visit another SCC $C^{\prime }$
   5. Select another start vertex $s_2\in C_2$ with largest max_finish(C) of all SCC except for $C$