# Strong Connectivity

Understand the different techniques used to implement strong connectivity efficiently.

## We'll cover the following

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.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy