SCC graph

Dependencies:

1. Path in Graph

Let $G = (V, E)$ be a directed graph. Let $S = \{ C_1, C_2, \ldots, C_k \}$ be the set of strongly connected components (SCCs) of $G$.

The SCC graph of $G$, denoted as $\operatorname{SCC}(G)$ or $G^{\textrm{SCC}}$ is the graph $(S, E^{\textrm{SCC}})$, where \[ (C_i, C_j) \in E^{\textrm{SCC}} \iff (i \neq j \wedge (\exists u \in C_i, \exists v \in C_j, (u, v) \in E)) \]

Dependency for: None

Info:

• Depth: 2
• Number of transitive dependencies: 5

Transitive dependencies:

1. /sets-and-relations/equivalence-classes
2. /sets-and-relations/relation-composition-is-associative
3. /sets-and-relations/equivalence-relation
4. Graph
5. Path in Graph