Strongly connected components

In a directed graph, vertices belong to the same strongly connected component when each can reach the other. SCC decomposition replaces every maximal mutual reachability group with one component.

Recognition signals

• “These states can all return to one another.”
• Group accounts, pages, or transitions into mutual-reachability regions.
• Detect cycles at component scale.
• Reduce a directed graph to a DAG before dynamic programming.
• Solve implication systems such as 2-SAT.

Why the condensation graph matters

Collapse each SCC into one super-vertex. Any cycle between super-vertices would mean those vertices were mutually reachable and should have been one SCC. Therefore the condensation graph is always a DAG.

This often changes the real problem from “work on a cyclic directed graph” to “work on a DAG of components.”

flowchart LR
  accTitle: Strongly connected components collapse cycles into a DAG
  accDescr: Two directed cycles and one singleton vertex collapse into three component nodes with one-way edges, producing an acyclic condensation graph.
  subgraph O["Original directed graph"]
    A0["0"] --> A1["1"]
    A1 --> A2["2"]
    A2 --> A0
    A2 --> B3["3"]
    B3 --> B4["4"]
    B4 --> B3
    B4 --> C5["5"]
  end
  subgraph C["Condensation graph"]
    X["SCC {0,1,2}"] --> Y["SCC {3,4}"]
    Y --> Z["SCC {5}"]
  end
  A0 -.->|"collapse"| X
  B3 -.->|"collapse"| Y
  C5 -.->|"collapse"| Z

After assigning component IDs, forget the internal cycles and solve the remaining problem on the condensation DAG whenever only inter-component relationships matter.

Kosaraju thinking flow

1. Build graph and reverse graph.
2. DFS the reverse graph; append each vertex after its descendants.
3. Process vertices in reverse finishing order on the original graph.
4. Every new DFS reached in step 3 is one complete SCC.

The first pass chooses an order in which the second pass cannot leak from an unassigned component into one that should be processed later.

Tarjan alternative

Tarjan uses one DFS, a stack, discovery indices, and low-link values. When low[u] == discovery[u], u is the root of an SCC; pop the stack through u.

Choose Kosaraju when two passes and a reverse graph make the proof easier. Choose Tarjan when a one-pass implementation or lower constant memory is important and you are comfortable with its stack invariant.

Complexity and traps

• Time: O(V + E).
• Space: O(V + E) for adjacency and bookkeeping.
• SCC is for directed graphs; undirected connected components are simpler.
• “In the DFS stack” is different from “visited.”
• After assigning component IDs, deduplicate condensation edges when their multiplicity does not matter.
• Recursive DFS may overflow on a deep graph; use an explicit stack when input depth is unbounded.

Reference

• Princeton: Directed Graphs and strong connectivity
• Princeton: Tarjan SCC API

Tested iterative Kosaraju template

PythonC++17C++11

def strongly_connected_components(graph: Sequence[Sequence[int]]) -> list[list[int]]:
    """Partition a directed graph with iterative Kosaraju traversal."""
    _validate_unweighted_graph(graph)
    visited = [False] * len(graph)
    finish_order: list[int] = []

    for start in range(len(graph)):
        if visited[start]:
            continue
        visited[start] = True
        stack = [(start, 0)]
        while stack:
            node, edge_index = stack[-1]
            if edge_index < len(graph[node]):
                neighbor = graph[node][edge_index]
                stack[-1] = (node, edge_index + 1)
                if not visited[neighbor]:
                    visited[neighbor] = True
                    stack.append((neighbor, 0))
            else:
                # Postorder records a vertex only after its suffix is complete.
                finish_order.append(node)
                stack.pop()

    reversed_graph: list[list[int]] = [[] for _ in graph]
    for node, neighbors in enumerate(graph):
        for neighbor in neighbors:
            reversed_graph[neighbor].append(node)

    component_of = [-1] * len(graph)
    components: list[list[int]] = []
    for start in reversed(finish_order):
        if component_of[start] != -1:
            continue
        component_id = len(components)
        component: list[int] = []
        stack = [start]
        component_of[start] = component_id
        while stack:
            node = stack.pop()
            component.append(node)
            for neighbor in reversed_graph[node]:
                if component_of[neighbor] == -1:
                    component_of[neighbor] = component_id
                    stack.append(neighbor)
        components.append(sorted(component))
    return components

inline std::vector<std::vector<int>> strongly_connected_components(
    const std::vector<std::vector<int>>& graph) {
  for (const auto& neighbors : graph) {
    for (const int neighbor : neighbors) {
      validate_vertex(neighbor, graph.size(), "neighbor");
    }
  }
  std::vector<bool> visited(graph.size(), false);
  std::vector<int> finish_order;
  for (int start = 0; start < static_cast<int>(graph.size()); ++start) {
    if (visited[start]) {
      continue;
    }
    visited[start] = true;
    std::vector<std::pair<int, std::size_t>> stack(1, {start, 0});
    while (!stack.empty()) {
      const int node = stack.back().first;
      std::size_t& edge_index = stack.back().second;
      if (edge_index < graph[node].size()) {
        const int neighbor = graph[node][edge_index++];
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          stack.push_back({neighbor, 0});
        }
      } else {
        // Postorder records a vertex only after its suffix is complete.
        finish_order.push_back(node);
        stack.pop_back();
      }
    }
  }

  std::vector<std::vector<int>> reversed(graph.size());
  for (int node = 0; node < static_cast<int>(graph.size()); ++node) {
    for (const int neighbor : graph[node]) {
      reversed[neighbor].push_back(node);
    }
  }
  std::vector<int> component_of(graph.size(), -1);
  std::vector<std::vector<int>> components;
  for (auto position = finish_order.rbegin(); position != finish_order.rend();
       ++position) {
    const int start = *position;
    if (component_of[start] != -1) {
      continue;
    }
    const int component_id = static_cast<int>(components.size());
    components.push_back(std::vector<int>());
    std::vector<int> stack(1, start);
    component_of[start] = component_id;
    while (!stack.empty()) {
      const int node = stack.back();
      stack.pop_back();
      components.back().push_back(node);
      for (const int neighbor : reversed[node]) {
        if (component_of[neighbor] == -1) {
          component_of[neighbor] = component_id;
          stack.push_back(neighbor);
        }
      }
    }
    std::sort(components.back().begin(), components.back().end());
  }
  return components;
}

inline std::vector<std::vector<int>> strongly_connected_components(
    const std::vector<std::vector<int>>& graph) {
  for (const auto& neighbors : graph) {
    for (const int neighbor : neighbors) {
      validate_vertex(neighbor, graph.size(), "neighbor");
    }
  }
  std::vector<bool> visited(graph.size(), false);
  std::vector<int> finish_order;
  for (int start = 0; start < static_cast<int>(graph.size()); ++start) {
    if (visited[start]) {
      continue;
    }
    visited[start] = true;
    std::vector<std::pair<int, std::size_t>> stack(1, {start, 0});
    while (!stack.empty()) {
      const int node = stack.back().first;
      std::size_t& edge_index = stack.back().second;
      if (edge_index < graph[node].size()) {
        const int neighbor = graph[node][edge_index++];
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          stack.push_back({neighbor, 0});
        }
      } else {
        // Postorder records a vertex only after its suffix is complete.
        finish_order.push_back(node);
        stack.pop_back();
      }
    }
  }

  std::vector<std::vector<int>> reversed(graph.size());
  for (int node = 0; node < static_cast<int>(graph.size()); ++node) {
    for (const int neighbor : graph[node]) {
      reversed[neighbor].push_back(node);
    }
  }
  std::vector<int> component_of(graph.size(), -1);
  std::vector<std::vector<int>> components;
  for (auto position = finish_order.rbegin(); position != finish_order.rend();
       ++position) {
    const int start = *position;
    if (component_of[start] != -1) {
      continue;
    }
    const int component_id = static_cast<int>(components.size());
    components.push_back(std::vector<int>());
    std::vector<int> stack(1, start);
    component_of[start] = component_id;
    while (!stack.empty()) {
      const int node = stack.back();
      stack.pop_back();
      components.back().push_back(node);
      for (const int neighbor : reversed[node]) {
        if (component_of[neighbor] == -1) {
          component_of[neighbor] = component_id;
          stack.push_back(neighbor);
        }
      }
    }
    std::sort(components.back().begin(), components.back().end());
  }
  return components;
}

Both passes use explicit stacks, so a long directed chain does not consume the language call stack. Component order is an implementation detail; membership is the contract.