Strongly Connected Components

## The definition, stated carefully Work in a **directed graph**: vertices joined by edges that point one way. Vertex `v` is **reachable** from `u` if some sequence of edges leads from `u` to `v`, always travelling in the direction each edge points. Reachability is one-directional; `v` reachable from `u` says nothing about getting back. `u` and `v` are **mutually reachable** when both `u -> ... -> v` and `v -> ... -> u` exist. A **strongly connected component** (SCC) is a *maximal* set of pairwise mutually reachable vertices — maximal meaning you cannot add another vertex to the set and keep the property. ## Why the components partition the graph Mutual reachability is an equivalence relation: - **Reflexive** — every vertex reaches itself by the empty path. - **Symmetric** — the definition already demands both directions. - **Transitive** — if `u` and `v` are mutually reachable and `v` and `w` are, concatenating paths gives `u <-> w`. Equivalence relations carve their domain into disjoint classes, and those classes are exactly the SCCs. Three consequences follow immediately, and each is a place interviews probe: 1. **Every vertex belongs to exactly one component.** Components never overlap and never leave a vertex out. 2. **A vertex on no directed cycle is its own component**, a singleton, because reflexivity alone qualifies it. Candidates who say "that vertex has no component" have quietly swapped the definition for "cycle". 3. **The count of components runs from 1 to V.** Exactly one component means the whole graph is strongly connected: everything reaches everything. Exactly `V` components means no directed cycle exists anywhere — the graph is acyclic. A useful equivalent phrasing: `u` and `v` share a component precisely when some closed directed walk passes through both. Note *walk*, not *simple cycle* — the `u -> v` path and the `v -> u` path may share vertices, so what you get is a closed walk, which is enough. ## The mistake: treating direction as decoration The common wrong move is to erase arrows and run ordinary connected-component labelling. That computes **weak connectivity**: whether the underlying undirected graph hangs together. It is a genuinely different question, and it is strictly weaker. The minimal counterexample is two vertices with one edge, `A -> B`. Erase direction and you see one piece. Respect direction and `B` reaches nothing, so `A` and `B` are two separate components. Scale that up to a call graph of services: an ordering service calls a pricing service, which calls a currency service, which calls nobody. Ignoring direction reports one clump of three. The truth is three components — nothing downstream can call back upstream, and that asymmetry is precisely the information you wanted. The reverse error also appears: assuming that because the graph is *weakly* connected it must be *strongly* connected "if there are enough edges". Edge count is irrelevant; a graph with a million edges arranged as a long one-way chain still has a million-plus singleton components. ## Related but distinct notions - **Weakly connected** — connected once directions are dropped. Implied by strongly connected, never the reverse. - **Reachable from a root** — one traversal from a chosen vertex reaches everything. That is weaker than strong connectivity too, because it says nothing about paths back to the root. - **Acyclic** — no directed cycles, which is the same as "every component is a singleton". ## What it costs Computing all SCCs is a linear-time job, O(V + E), using either a two-pass finish-order method or a one-pass low-link method. That is the same order as a single traversal, which is why an interviewer expects you to reach for it without hesitation rather than proposing anything pairwise. Checking reachability for every pair separately would cost O(V * (V + E)) and is the answer to avoid. ## How to say it in an interview "A strongly connected component is a maximal group of vertices where every vertex reaches every other along directed edges. Mutual reachability is an equivalence relation, so the components partition the vertices — a vertex on no cycle is its own singleton. Ignoring direction answers a weaker question: two vertices joined by a single one-way edge look connected but form two components. Finding all of them is linear, O(V + E)."