Strong Connectivity

Let’s go back to the proper definition of connectivity in directed graphs. Recall that one vertex $u$ can reach another vertex $v$ in a directed graph $G$ if $G$ contains a directed path from $u$ to $v$, and that $reach(u)$ denotes the set of all vertices that $u$ can reach. Two vertices $u$ and $v$ are strongly connected if $u$ can reach $v$ and $v$ can reach $u$. A directed graph is strongly connected if and only if every pair of vertices is strongly connected.

Tedious definition-chasing implies that strong connectivity is an equivalence relation over the set of vertices of any directed graph, just like connectivity in undirected graphs. The equivalence classes of this relation are called the strongly connected components or, more simply, the strong components of $G$. Equivalently, a strong component of $G$ is a maximal strongly connected subgraph of $G$. A directed graph $G$ is strongly connected if and only if $G$ has exactly one strong component; at the other extreme, $G$ is a dag if and only if every strong component of $G$ consists of a single vertex.