Strongly Connected Component

These are maximal subsets of vertices reachable from each other in a directed graph. $\{e,o\}$, $\{f,g,h,k\}$, $\{m\}$

Definition

Consider definition of SCC: $S\subset V$ s.t $\forall v\in S,\forall u\in S,u\ne v\Rightarrow \exists \text{ path from }u\to v$

Algorithms

• Kosaraju’s Algorithm