strongly connected components
On a one-way street map, being able to drive from A to B does not mean you can drive back from B to A. A strongly connected component captures the places that are mutually reachable: a maximal group of vertices in a directed graph where you can get from every vertex to every other vertex and back, all respecting the arrow directions. Within one SCC you can take a round trip between any two members; between different SCCs the travel is one-way at best.
Precisely, two vertices u and v are in the same strongly connected component if there is a directed path from u to v AND a directed path from v back to u. This is an equivalence relation (reflexive, symmetric by definition, and transitive by gluing paths), so it carves the vertices into disjoint classes — the SCCs. A wonderful structural fact follows: if you shrink each SCC down to a single super-vertex, the resulting graph of super-vertices, called the condensation, is always a DAG — it has no cycles, because any cycle among SCCs would merge them into one larger SCC. So a directed graph is, at the coarse level, a DAG of strongly connected blobs, each blob internally a tangle of two-way reachability. Computing the SCCs and this condensation is the standard first move for understanding a directed graph's large-scale shape.
SCCs show up everywhere directed mutual reachability matters: deadlock cycles among processes, groups of web pages that all link to each other, variables forced equal in a 2-SAT implication graph, modules with circular dependencies. Two linear-time algorithms compute all SCCs in O(n + m): Kosaraju's (two passes of DFS, one on the graph and one on its edge-reversed copy) and Tarjan's (a single DFS tracking low-link values). The honest contrast to keep clear: undirected connected components only ask whether you can get between two vertices at all, while SCCs demand you can return — so the two notions genuinely differ on a directed graph, and a graph that is one connected component undirected can shatter into many SCCs once you respect the arrows.
Directed edges: a->b, b->c, c->a, c->d, d->e, e->d. SCCs: {a,b,c} (a cycle a-b-c-a lets you round-trip among them) and {d,e} (d->e->d). Vertex d is reachable from the first SCC but cannot return, so they stay separate. The condensation {a,b,c} -> {d,e} is a 2-node DAG.
Contract each SCC to one node and the arrows between blobs never form a cycle — the condensation is always a DAG.
An SCC needs reachability both ways; a single directed path one direction is not enough. Do not confuse SCCs with undirected connected components — respecting arrow directions can split one undirected piece into many SCCs.