SCC Condensation, in depth: the component DAG, dynamic programming on it, bitset reachability and making a graph strongly connected

Why the condensation is always a DAG

Define the condensation C(G) as follows: one node per SCC, and an edge from component X to component Y whenever some original edge u to v has u in X, v in Y and X different from Y. Edges inside a component are dropped, because they say nothing about order between components.

Why is C(G) acyclic? Suppose it had a cycle X1, X2, ..., Xm, X1 with m at least 2. Every vertex in X1 can reach every vertex in X2 by walking to the edge that leaves X1 and following it, and the same holds around the cycle, so every vertex in X2 can also reach back into X1. Then X1 and X2 are mutually reachable, so they belong to the same SCC, which contradicts them being different maximal components. The argument is short, but it gives you a useful debugging rule: if your condensation ever contains a cycle, your component labels are wrong, not your graph.

Two properties follow that the rest of this article relies on. First, a walk in G can stay inside a component as long as it likes and visit every vertex there, because each vertex is reachable from every other. Second, u reaches v in G exactly when comp(u) reaches comp(v) in C(G). So any question about reachability, or about walks that may repeat vertices, can be answered on the much smaller DAG.

Building it with deduplicated edges

Building C(G) is a second linear pass once every vertex has a label. For each edge u to v, map it to the pair (comp[u], comp[v]), skip it if both are equal, and skip it if the pair was already emitted. A hash set works; for very large graphs, sorting the pairs or bucketing them by source component and deduplicating each bucket with a marker array is faster and uses less memory.

The order of the labels is the part people get wrong. An iterative Tarjan implementation assigns component ids in the order components are completed, and a component is completed only after everything it can reach. So Tarjan ids are a reverse topological order: every condensation edge goes from a higher id to a lower id. Kosaraju, which runs its second pass on the transposed graph in decreasing finish time, emits components in topological order instead. The snippet below uses Tarjan, and the assertion at the end is worth keeping in production code because it catches a swapped convention immediately.

def condense(n, adj, comp, k):
    """comp[v] in 0..k-1 from Tarjan; returns deduplicated DAG adjacency."""
    seen = set()
    dag = [[] for _ in range(k)]
    for u in range(n):
        for v in adj[u]:
            a, b = comp[u], comp[v]
            if a != b and (a, b) not in seen:
                seen.add((a, b))
                dag[a].append(b)
    # Tarjan numbers components sinks-first: every DAG edge points to a smaller id.
    assert all(a > b for a in range(k) for b in dag[a])
    return dag

Worked example

The worked example has eight vertices with integer weights, which you can think of as coins on each room of a one-way maze. Vertices 0, 1 and 2 form a triangle, 3 and 4 point at each other, and so do 5 and 6. Vertex 7 has no outgoing edges. Two edges, 0 to 3 and 2 to 3, both cross from A to B, so the condensation keeps only one of them.

Running Tarjan on this graph gives the labels D=0, C=1, B=2, A=3: the sink first, the source last. The DAG has five edges: A to B, A to C, B to C, B to D and C to D. Component weights are A=8, B=8, C=6, D=9.

Dynamic programming over components

Question: starting anywhere, walking along edges, and collecting each vertex weight the first time you visit it, what is the most you can collect? On a general graph with cycles this sounds like a search problem. On the condensation it is a longest-path DP, because inside a component you can collect everything and still leave by any outgoing edge, and between components you can never come back. Each component contributes its whole weight, and best[X] = weight[X] + max of best over the successors of X.

With Tarjan ids, iterating components in increasing id order visits every successor before its predecessors, so no separate topological sort is needed:

def best_walk(n, adj, weight):
    comp, k = scc_tarjan(n, adj)          # iterative, ids in reverse topological order
    dag = condense(n, adj, comp, k)
    cw = [0] * k
    for v in range(n):
        cw[comp[v]] += weight[v]
    best = [0] * k
    for c in range(k):                     # sinks first
        best[c] = cw[c] + max((best[d] for d in dag[c]), default=0)
    return max(best)

For the example, best[D]=9, best[C]=6+9=15, best[B]=8+max(15, 9)=23 and best[A]=8+23=31. The answer 31 is the sum of all weights, because a walk A, B, C, D exists. Delete edge 4 to 5 and the DAG loses B to C, so no walk visits all four components any more: A, B, D collects 8+8+9=25 and A, C, D collects 8+6+9=23, so the optimum drops to 25. Small edits like that are exactly what a test suite should contain.

The same skeleton answers many variants: the number of distinct walks between two components (sum instead of max, modulo a prime), the earliest finish time when each component is a task group, or the minimum cost to reach a sink. The only rule is to decide what a component contributes as a whole, which is usually its sum, its minimum, or a flag saying it contains a cycle.

Reachability with bitsets

All-pairs reachability on a graph with V vertices costs O(V(V+E)) by running a search from each vertex. On the condensation, process components sinks first and give each one a bitset: its own bit OR the bitsets of its successors. Each union is a word-parallel OR, so the total is O(k * (k + E_c) / 64) word operations, where E_c is the number of condensation edges.

def reach_bitsets(k, dag):
    reach = [0] * k            # Python ints as bitsets; use numpy uint64 rows in production
    for c in range(k):         # Tarjan ids: successors already done
        r = 1 << c
        for d in dag[c]:
            r |= reach[d]
        reach[c] = r
    return reach

def reaches(u, v, comp, reach):
    return (reach[comp[u]] >> comp[v]) & 1 == 1

The memory is the catch: k squared bits. At k = 100,000 components that is 1.25 GB, and at a million it is 125 GB. When the matrix will not fit, keep bitsets only for components that are queried often, compute rows in blocks of a few thousand target components at a time, or fall back to a search from comp(u) on the DAG per query, which is still much smaller than the raw graph.

Sources, sinks and making a graph strongly connected

A classic question: what is the minimum number of edges to add so that the whole graph becomes strongly connected? Let s be the number of source components (in-degree 0 in C(G)) and t the number of sinks (out-degree 0). If C(G) has a single node, the answer is 0. Otherwise it is max(s, t), a result due to Eswaran and Tarjan in their 1976 paper on augmentation problems.

The lower bound is easy: every source needs at least one new incoming edge and every sink at least one new outgoing edge, and one added edge can serve one sink and one source at a time. The upper bound needs care. Pairing sinks to sources arbitrarily can leave two separate cycles, so the constructive algorithm first matches sources to sinks they can reach, links those pairs in a ring, then attaches the leftovers. If you only need the count, use the formula and keep the single-component special case; forgetting it returns 1 for a graph that is already strongly connected, because its one node is both a source and a sink. In the example s = 1 (A) and t = 1 (D), so one edge, D to A such as 7 to 0, makes the graph strongly connected.

def min_edges_to_strong(k, dag):
    if k == 1:
        return 0
    indeg = [0] * k
    for c in range(k):
        for d in dag[c]:
            indeg[d] += 1
    sources = sum(1 for c in range(k) if indeg[c] == 0)
    sinks = sum(1 for c in range(k) if not dag[c])
    return max(sources, sinks)

Where the condensation earns its keep

The condensation shows up wherever a system has mutual dependencies but still needs an order.

• Build systems and package managers. Components of size two or more in the import graph are dependency cycles. Report each as one unit, then build components in topological order; see topological sort for deterministic orders and levels.
• Compilers. Mutually recursive functions form an SCC of the call graph and are analysed together to a fixed point, then summaries flow up the DAG.
• Datalog and rule engines. Stratified negation needs the predicate dependency graph condensed; a negative edge inside one component means the program cannot be stratified.
• 2-SAT. The assignment is read off the component order of the implication graph, as shown in 2-SAT via SCC.
• Deadlock and service graphs. An SCC of size two or more in a wait-for graph is a deadlock; in a service call graph it is a set of services that cannot be deployed independently.

Failure modes

Most bugs here are about order and bookkeeping, not about the SCC algorithm itself.

When the graph changes

Graphs change. Adding an edge from component X to Y merges every component on any path from Y back to X, if such a path exists; otherwise it just adds a DAG edge. Deleting an edge inside a component may split it. Research algorithms maintain SCCs incrementally, but they are intricate, and for most systems the honest answer is that the full recomputation is O(V + E) with small constants. Batch edits, recompute on a timer or on commit, and version the labels so readers never see a half-updated map.

If edits are frequent and only additions, a cheap check helps: before inserting X to Y, test whether Y reaches X in the current DAG. If not, append the edge and you are done; only the merge case needs a rebuild.

Trade-offs

What to do next

1. Pick a real graph you own, such as imports, service calls or job dependencies, and compute its condensation.
2. Add the assertion that every DAG edge goes from a higher Tarjan id to a lower one, and run it in CI.
3. List components with more than one vertex; those are your cycles. Give each an owner.
4. Implement the best-walk DP on the example above and check you get 31, then 25 after deleting edge 4 to 5.
5. Write a brute-force reachability checker for graphs of up to 12 vertices and compare it with the bitset version on random inputs.
6. Estimate k squared over 8 bytes before choosing full bitset reachability.
7. Decide how the condensation is refreshed when edges change, and version the labels.