Find strongly connected components for an undirected graph
programming
Statement
Find strongly connected components in an directed graph
Given a directed graph $G = (V,E)$ how can we find a mapping from it’s vertices $V$ to the strongly connected components of $G$.
Solutions
- DFS for finding strongly connected components
- This runs in $O(\vert V \vert \cdot \vert E \vert)$ time.
- It also outputs the strongly connected components in a reverse topologically sort.