Skip to content

Condensation Graph

Condensation: SCCs compressed into single nodes forming a DAG

Collapse Cycles, Unlock DP

Directed graphs with cycles can't be topologically sorted. DP on them seems impossible. But here's the trick: every SCC is a cycle (or a single node). Contract each SCC into a single super-node. The result is a DAG -- the condensation graph. Now you can topo-sort it and run DP. This pattern unlocks a whole class of problems.

What Is the Condensation Graph?

Given a directed graph G:

  1. Find all SCCs. Assign each node to its SCC.
  2. Create a new graph where each SCC is a single node.
  3. For each edge (u, v) in G where comp[u] != comp[v], add edge (comp[u], comp[v]) to the condensation.
  4. Remove duplicate edges.

The result is guaranteed to be a DAG. Why? If two super-nodes had a cycle between them, the nodes in both SCCs could reach each other, making them one big SCC. That contradicts the maximality of SCCs.

Building the Condensation

// After Kosaraju's: comp[u] = SCC id for each node
// numSCC = total number of SCCs

vector<vector<int>> dag(numSCC);
vector<int> indeg(numSCC, 0);
set<pair<int,int>> seen;

for (int u = 1; u <= n; u++) {
    for (int v : adj[u]) {
        if (comp[u] != comp[v]) {
            if (seen.insert({comp[u], comp[v]}).second) {
                dag[comp[u]].push_back(comp[v]);
                indeg[comp[v]]++;
            }
        }
    }
}

⚠ Gotcha. Without deduplication, the condensation can have O(E) edges even though only O(V) are unique. The set<pair<int,int>> prevents duplicates. For tighter memory, sort and deduplicate instead.

CSES Coin Collector

Problem: N rooms, M one-way corridors. Each room has some coins. You start in any room, collect coins, and follow corridors. You can visit a room multiple times but only collect its coins once. Maximize total coins collected.

Key observation: If two rooms are in the same SCC, you can visit both. So you always collect all coins in every SCC you enter. The problem reduces to: find the path in the condensation DAG that maximizes the sum of SCC coin totals.

Steps:

  1. Find SCCs with Kosaraju's.
  2. Sum coins per SCC.
  3. Build condensation DAG.
  4. DP longest path on the DAG.
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
vector<int> adj[MAXN], radj[MAXN];
int comp[MAXN];
bool vis[MAXN];
vector<int> order;
long long coins[MAXN];

void dfs1(int u) {
    vis[u] = true;
    for (int v : adj[u])
        if (!vis[v]) dfs1(v);
    order.push_back(u);
}

void dfs2(int u, int c) {
    comp[u] = c;
    for (int v : radj[u])
        if (comp[v] == -1) dfs2(v, c);
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> coins[i];
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        radj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++)
        if (!vis[i]) dfs1(i);

    memset(comp, -1, sizeof(comp));
    int numSCC = 0;
    for (int i = (int)order.size() - 1; i >= 0; i--)
        if (comp[order[i]] == -1)
            dfs2(order[i], numSCC++);

    // Sum coins per SCC
    vector<long long> sccCoins(numSCC, 0);
    for (int i = 1; i <= n; i++)
        sccCoins[comp[i]] += coins[i];

    // Build condensation DAG
    vector<vector<int>> dag(numSCC);
    set<pair<int,int>> seen;
    for (int u = 1; u <= n; u++)
        for (int v : adj[u])
            if (comp[u] != comp[v])
                if (seen.insert({comp[u], comp[v]}).second)
                    dag[comp[u]].push_back(comp[v]);

    // DP: longest path on DAG
    // Kosaraju's comp 0 is a source SCC.
    // Process in order 0, 1, ..., numSCC-1
    // (this is topological order of condensation).
    vector<long long> dp(numSCC);
    for (int c = 0; c < numSCC; c++)
        dp[c] = sccCoins[c];

    for (int c = 0; c < numSCC; c++)
        for (int nc : dag[c])
            dp[nc] = max(dp[nc], dp[c] + sccCoins[nc]);

    cout << *max_element(dp.begin(), dp.end()) << "\n";
}

Trace on small example:

Graph: 1->2, 2->3, 3->1, 3->4, 4->5, 5->4. Coins: [5, 3, 2, 7, 1].

Step Result
SCCs {1,2,3} (comp=0), {4,5} (comp=1)
SCC coins [10, 8]
DAG edges 0 -> 1
DP dp[0] = 10, dp[1] = max(8, 10+8) = 18
Answer 18

💡 Key insight. The DP processes SCCs in topological order. Kosaraju's naturally gives SCCs numbered in topological order of the condensation (comp 0 is a source, comp numSCC-1 is a sink). No separate topo sort needed.

CSES Flight Routes Check

Problem: N cities, M flights (directed). Check if you can fly from any city to any other city. If not, print a pair of cities with no route between them.

Translation: The graph is strongly connected if and only if there is exactly 1 SCC.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
vector<int> adj[MAXN], radj[MAXN];
int comp[MAXN];
bool vis[MAXN];
vector<int> order;
vector<int> members[MAXN];

void dfs1(int u) {
    vis[u] = true;
    for (int v : adj[u])
        if (!vis[v]) dfs1(v);
    order.push_back(u);
}

void dfs2(int u, int c) {
    comp[u] = c;
    members[c].push_back(u);
    for (int v : radj[u])
        if (comp[v] == -1) dfs2(v, c);
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        radj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++)
        if (!vis[i]) dfs1(i);

    memset(comp, -1, sizeof(comp));
    int numSCC = 0;
    for (int i = (int)order.size() - 1; i >= 0; i--)
        if (comp[order[i]] == -1)
            dfs2(order[i], numSCC++);

    if (numSCC == 1) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
        // Find two nodes in different SCCs.
        // Source SCC (comp 0) can reach others but
        // others can't reach it. Pick a node in comp 0
        // and a node in another SCC.
        // Node in comp 0 can't be reached from comp 1.
        cout << members[1][0] << " " << members[0][0] << "\n";
    }
}

⚠ Gotcha. The problem asks for a pair (a, b) where there's no route from a to b. A node in a non-source SCC can't reach the source SCC, so print (non-source node, source node). Getting the direction wrong gives wrong answer.

The Condensation Pattern

Almost every SCC problem follows this template:

  1. Find SCCs (Kosaraju's or Tarjan's).
  2. Aggregate per-SCC values (sum coins, count nodes, etc.).
  3. Build condensation DAG (deduplicate edges).
  4. DP on the DAG (longest path, reachability, counting).

The DP is always straightforward because the condensation is a DAG. The hard part is recognizing that the problem has SCC structure.

Problem Variant What to Aggregate DP Type
Max coins Sum of coin values Longest path
Can all nodes communicate? SCC count Check count == 1
Min cost to connect all SCC in/out degrees Count sources/sinks
Which nodes reach a cycle? SCC sizes Reachability (next lesson)

Try It

The starter code has Kosaraju's ready. Add condensation construction and DP.

Test case (Coin Collector): 

Input:
5 6
5 3 2 7 1
1 2
2 3
3 1
3 4
4 5
5 4

Output:
18

Test case (Flight Routes Check): 

Input:
4 5
1 2
2 3
3 1
1 4
4 1

Output:
YES

Problems

Problem Link Difficulty
CSES Coin Collector cses.fi/problemset/task/1686 Medium
CSES Flight Routes Check cses.fi/problemset/task/1682 Easy