scc

Strongly Connected Component

Strong connected component | Wikipedia

Definition A strongly connected component of a directed graph

$G=(V,E)$ is a maximal set of vertices $C\subseteq V$ such that for every pair of vertices $u,v\in C$, both $u⇝v$ and $v⇝u$, i.e. reachable from each other.

• Component graph: $G^{\text{SCC}}=(V^{\text{SCC}},E^{\text{SCC}})$, with the “contraction” technique.
• Component graph is acyclic!
• Procedures for computing
  • Call DFS on $G$ to compute finish times $u.f$ for each vertex
  • Create $G^{\mathrm{T}}$
  • Call DFS of $G^{\mathrm{T}}$, but in the main loop consider vertices in order of decreasing $u.f$
  • Output vertices of each tree