Question 13

Two vertices $u$ and $v$ belong to the same strongly connected component (SCC) in a directed graph $G = (V, E)$ if and only if there is a directed path from $u$ to $v$ and a directed path from $v$ to $u$.

In the transpose graph $G_2 = (V, E_2)$ where $E_2 = \{(u, v) \mid (v, u) \in E\}$, every edge is reversed in direction.

• A path $u \rightsquigarrow v$ in $G$ corresponds directly to a path $v \rightsquigarrow u$ in $G_2$.
• Therefore, $u$ and $v$ are mutually reachable in $G$ if and only if they are mutually reachable in $G_2$.

Consequently, the equivalence classes of mutual reachability are identical, so $G_2$ has the exact same strongly connected components as $G$.