Why is a directed graph's condensation into strongly connected components always a DAG?
answer
- start from what maximal means
- assume two component-nodes form a cycle
- chain the paths through both components
- now those vertices are mutually reachable
- so they were one component all along
basics
~20 sContracting each strongly connected component to one node can never leave a cycle. A cycle through two component-nodes would make all their vertices mutually reachable, so those components would have been a single larger component — which maximality already forbids.
solid answer
~50 sBuild the condensation by replacing each strongly connected component with one node and keeping an edge `C -> D` whenever some vertex of `C` has an edge to some vertex of `D`. Suppose the result had a cycle `C -> D -> ... -> C`. Then every vertex of `C` reaches every vertex of `D` and vice versa, so `C` and `D` are mutually reachable — meaning they were never maximal, contradicting the definition of a component. So no cycle can survive contraction, and the result is a DAG. This is why the decomposition is useful rather than decorative: over a call graph of services, each component is an indivisible unit — services inside one cannot be pulled apart independently — while the acyclic skeleton between components shows which units genuinely have a one-way relationship. No separate cycle check on the condensation is ever needed.
go deeper
Know what the condensation is: one node per strongly connected component, edges kept only between different components. Remember the headline result that it is always acyclic.
Give the contradiction argument out loud — a cycle across two component-nodes makes their vertices mutually reachable, breaking maximality. Also know that internal edges vanish, so no self-loops appear.
Use it as a diagnostic: identify which parts of a real directed dependency graph form indivisible units and which relationships are genuinely one-way, and say what each fact rules in or out.
Own the consequence: a large component is a structural statement that a set of parts cannot be separated, versioned, or reasoned about independently, and shrinking one is a design programme with a cost, not a cleanup ticket.
## What the condensation is Given a directed graph `G`, compute its strongly connected components — the maximal sets of mutually reachable vertices. The **condensation** (also called the component graph) has one node per component, and an edge from component `C` to component `D` (with `C != D`) whenever `G` contains at least one edge from a vertex of `C` to a vertex of `D`. Edges that ran *inside* a component vanish; parallel edges between the same two components collapse to one. Since the components partition the vertices, the condensation has between 1 and V nodes, and it can be built in O(V + E) once the components are labelled: scan every edge once and keep it if its endpoints carry different labels. ## The proof that it is acyclic By contradiction. Assume the condensation contains a directed cycle visiting distinct component-nodes `C1 -> C2 -> ... -> Ck -> C1`, with `k >= 2`. Each edge `Ci -> Ci+1` came from a real edge between a vertex of `Ci` and a vertex of `Ci+1`. Inside each component, every vertex reaches every other. Chain those facts: pick any `u` in `C1` and any `v` in `C2`. Travel inside `C1` to the tail of the edge into `C2`, cross it, then travel inside `C2` to `v` — so `u` reaches `v`. Follow the rest of the cycle the same way and you return from `v` to `u`. Therefore `u` and `v` are mutually reachable while lying in different components. That is impossible. Mutual reachability is an equivalence relation and components are its classes, so mutually reachable vertices are in the *same* class. Equivalently: `C1 ∪ C2` would be a mutually reachable set strictly containing `C1`, so `C1` was never maximal. The contradiction kills the assumption; no cycle can exist. Two corollaries fall out of the construction rather than the proof: - **No self-loops.** Edges within a component are dropped by definition, so a component-node never points at itself, even when its vertices are riddled with cycles. - **The condensation is a single node exactly when `G` is strongly connected**, and has `V` nodes with all of `G`'s edges preserved exactly when `G` was already acyclic. ## Why anyone bothers The condensation is the *shape of the one-way structure* hiding inside a tangled directed graph. Take a call graph of a service estate, one node per service, an edge for "calls". Raw, it looks like spaghetti. Condensed, you get two different kinds of information: - **Inside a component**: a set of services that all, transitively, call each other. They form one indivisible unit for reasoning purposes. You cannot describe any of them as "downstream" of another, and pulling one out on its own is not a local change — an engineer proposing to extract a single service from a nine-service component is proposing to break the mutual reachability, which is a design decision, not a refactor. - **Between components**: genuinely one-way relationships. Because the skeleton is acyclic, questions that only make sense on acyclic structures — longest chain, dynamic programming over the component graph, "what can reach this unit" — are all well-posed on it. Two shapes are worth naming. A component-node with **no incoming edges** is a *source*: nothing outside can reach its vertices. A component-node with **no outgoing edges** is a *sink*: once you enter it, you never leave. A DAG always has at least one of each. ## The failure modes - **"The condensation might still contain cycles, so check."** It cannot, by the argument above. Running cycle detection on it is wasted work and signals that the candidate has memorised the construction without the maximality argument. - **"Contract the cycles."** Contracting individual cycles is not the same operation. Two cycles sharing a vertex belong to one component; contracting each cycle separately produces something that can still cycle. The unit of contraction is the maximal component. - **"Vertices outside cycles get dropped."** They do not — each becomes a singleton node in the condensation. The condensation has exactly as many nodes as there are components, covering every original vertex. - **Thinking one component may become several condensation nodes**, or that components can share a vertex. The partition rules both out. ## How to say it in an interview "Replace each strongly connected component with one node, keep the edges that crossed between components. If the result had a cycle, all the vertices on it would be mutually reachable, so those components would really have been one component — which contradicts maximality. So the condensation is always acyclic, with no self-loops, and it is exactly the one-way skeleton of the original graph."
- Can the condensation contain a self-loop on a component-node?No. Edges whose endpoints lie in the same component are dropped during contraction, so only edges between distinct components survive. A component full of internal cycles still becomes a single node with no loop on itself.
- What does a condensation node with no incoming edges tell you?It is a source component: no vertex outside it can reach any vertex inside it. Since the condensation is acyclic it must have at least one source and at least one sink, the sink being a component nothing can leave once entered.
- Why is contracting every cycle you find not the same as building the condensation?Cycles that share vertices belong to one component, and contracting them one at a time can leave the result still cyclic. The correct unit is the maximal mutually reachable set, which merges all overlapping cycles at once.
saying these in an interview costs you the question
- Says the condensation may still contain directed cycles
- Contracts individual cycles instead of maximal components
- Claims vertices outside cycles disappear from the condensation
- Thinks one component can map to several condensation nodes
- Runs a separate cycle check on the condensation to be safe