strongly connected components

strongly connected components expose local communities in a graph.
constituents graph V,E
requirements strongly connected: for all v,w \in V, there is a path from v \to w, and there’s a path for w \to v.
We can decompose a graph into strongly connected components where a subgraph is strongly connected. (i.e. they form equivalence class under “is strongly connected.”)
additional information Kosaraju’s Algorithm A way to find strongly connected components in linear time O\left(n+m\right).
naive solution Use O\left(n^{2}\right) rounds to DFS from each node and check if the nodes are in a particular strongly connected component, or make a new one.
why do we care? they tell you about communities in a graph structure some algorithms only make sense on SCCs (PageRank eigenvector centrality) condensation graph strongly connected components form a directed acyclic graph, which is useful for analysis.
The condensation graph forms a DAG
Proof idea: if there are edges both ways, there would be a way to go from each component to another and hence the SCC would collapse.
finishing time: largest finish time of any element starting time: smallest starting time of any element