Strongly Connected Components, usually abbreviated as SCCs, are one of the most important structures in directed graphs. The central idea is simple: divide the graph into maximal groups of vertices where every vertex can reach every other vertex in the same group.

Formally, two vertices u and v belong to the same SCC if:

u ~> v
v ~> u

where ~> means that a directed path exists.

Reachability vs. strong connectivity

Consider:

A -> B -> C

C is reachable from A, but A is not necessarily reachable from C. Therefore A and C are not strongly connected.

Now consider a cycle:

A -> B -> C
^         |
|_________|

Every vertex can eventually reach every other vertex, so {A, B, C} forms one SCC.

The word maximal matters: an SCC contains as many vertices as possible while preserving mutual reachability.

Why SCCs matter

SCCs are useful whenever a directed system contains circular or mutually reachable relationships. Common applications include:

• detecting circular dependencies between software modules;
• finding cyclic dependency groups between microservices;
• analyzing call graphs and control-flow graphs;
• identifying mutually reachable states in state machines;
• studying directed social networks;
• simplifying large directed graphs;
• dependency analysis in build systems and package managers;
• web-link and document-link analysis.

Kosaraju and Tarjan

Two classic algorithms find SCCs in linear time:

O(V + E)

• Kosaraju's algorithm uses two DFS passes and a reversed graph.
• Tarjan's algorithm uses one DFS, a stack, and low-link values.

Kosaraju is often easier to learn, so this guide uses it as the main implementation.

How Kosaraju's algorithm works

Kosaraju has three main stages:

1. Run DFS on the original graph and record vertices by finishing time.
2. Reverse every directed edge.
3. Process vertices in decreasing finishing-time order on the reversed graph.

Each DFS tree created in stage three is exactly one SCC.

Stage 1: finishing order

For:

A -> B -> C

a DFS beginning at A may finish in this order:

C, B, A

Kosaraju cares about the time at which the complete DFS exploration of a vertex finishes, not only when the vertex is first discovered.

Stage 2: reverse the graph

If the original graph contains:

A -> B
B -> C
C -> A
C -> D

the reversed graph contains:

B -> A
C -> B
A -> C
D -> C

Reversing edges does not destroy the internal mutual reachability of an SCC.

Stage 3: DFS on the reversed graph

Take vertices from the end of the finishing-order stack. Whenever the selected vertex has not yet been visited, start a new DFS in the reversed graph. All vertices discovered by that DFS belong to one SCC.

Why the algorithm works

Imagine collapsing each SCC into one super-node. The resulting graph is called the condensation graph.

A condensation graph is always a DAG. If it contained a cycle, the SCCs on that cycle would actually be mutually reachable and therefore should have been one larger SCC.

The first DFS gives an order related to this DAG. After reversing the graph, processing vertices in decreasing finishing time isolates one SCC at a time instead of leaking into another component.

Complete JavaScript implementation

function kosaraju(graph) {
  const visited = new Set();
  const order = [];

  const nodes = new Set(Object.keys(graph));

  for (const neighbors of Object.values(graph)) {
    for (const node of neighbors) nodes.add(node);
  }

  function dfs1(node) {
    visited.add(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) dfs1(next);
    }

    order.push(node);
  }

  for (const node of nodes) {
    if (!visited.has(node)) dfs1(node);
  }

  const reversed = {};

  for (const node of nodes) {
    reversed[node] = [];
  }

  for (const [from, neighbors] of Object.entries(graph)) {
    for (const to of neighbors) {
      reversed[to].push(from);
    }
  }

  visited.clear();

  const components = [];

  function dfs2(node, component) {
    visited.add(node);
    component.push(node);

    for (const next of reversed[node] ?? []) {
      if (!visited.has(next)) dfs2(next, component);
    }
  }

  while (order.length) {
    const node = order.pop();

    if (!visited.has(node)) {
      const component = [];
      dfs2(node, component);
      components.push(component);
    }
  }

  return components;
}

Example:

const graph = {
  A: ["B"],
  B: ["C", "E"],
  C: ["A", "D"],
  D: ["E"],
  E: ["D"],
  F: ["E", "G"],
  G: ["F"]
};

console.log(kosaraju(graph));

A valid result is equivalent to:

[
  ["F", "G"],
  ["A", "B", "C"],
  ["D", "E"]
]

The order of the components or vertices inside them may differ without changing correctness.

TypeScript implementation

type Graph = Record<string, string[]>;

function stronglyConnectedComponents(graph: Graph): string[][] {
  const nodes = new Set<string>(Object.keys(graph));

  for (const neighbors of Object.values(graph)) {
    neighbors.forEach((node) => nodes.add(node));
  }

  const visited = new Set<string>();
  const order: string[] = [];

  const dfsOrder = (node: string): void => {
    visited.add(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) dfsOrder(next);
    }

    order.push(node);
  };

  nodes.forEach((node) => {
    if (!visited.has(node)) dfsOrder(node);
  });

  const reversed: Graph = {};

  nodes.forEach((node) => {
    reversed[node] = [];
  });

  for (const [from, neighbors] of Object.entries(graph)) {
    for (const to of neighbors) {
      reversed[to].push(from);
    }
  }

  visited.clear();

  const result: string[][] = [];

  const collect = (node: string, component: string[]): void => {
    visited.add(node);
    component.push(node);

    for (const next of reversed[node] ?? []) {
      if (!visited.has(next)) collect(next, component);
    }
  };

  while (order.length) {
    const node = order.pop()!;

    if (!visited.has(node)) {
      const component: string[] = [];
      collect(node, component);
      result.push(component);
    }
  }

  return result;
}

Condensation graph

Suppose the SCCs are:

S1 = {A, B, C}
S2 = {D, E}
S3 = {F}

After collapsing each SCC into one node, we may get:

S1 -> S2 -> S3

This DAG representation is valuable because many problems are much easier on DAGs than on arbitrary directed graphs.

Real-world example: circular module dependencies

Suppose:

Auth -> User
User -> Payment
Payment -> Auth

These three modules form a dependency cycle. SCC analysis groups them into one component and shows that they are tightly coupled.

Real-world example: microservices

If service A depends on B, B on C, and C on A, then a failure or deployment decision in one service may affect the whole cyclic group. SCCs expose this structure.

Real-world example: state machines

SCCs can reveal sets of states in which the system can move around and eventually return to its starting state. That is useful for detecting loops and recurrent behavior.

Complexity

Kosaraju performs:

• one DFS on the original graph;
• one pass to build the reversed graph;
• one DFS on the reversed graph.

Therefore:

Time:  O(V + E)
Space: O(V + E)

The extra space comes mainly from the reversed graph, visited sets, the finishing-order stack, recursion, and the result.

Important edge cases

• An isolated vertex is an SCC by itself.
• A vertex with a self-loop is still a one-vertex SCC.
• If the whole graph is strongly connected, there is exactly one SCC.
• If the graph is a DAG, every vertex is its own SCC.
• Vertices that only appear in adjacency lists must still be included in the graph.
• Output order is usually not semantically important.

SCC vs. connected components

Connected components are enough for undirected graphs because reachability is naturally symmetric.

For directed graphs:

A -> B

A can reach B, but B cannot necessarily reach A. SCCs explicitly require reachability in both directions.

SCC vs. cycle detection

Every SCC with more than one vertex contains a directed cycle, but finding SCCs is not the same as finding one cycle.

Cycle detection asks whether a cycle exists or identifies particular cycles.

SCC decomposition partitions the entire graph into maximal mutually reachable regions.

Kosaraju vs. Tarjan

Kosaraju:

• easier to understand;
• two DFS passes;
• requires a reversed graph.

Tarjan:

• one DFS;
• no reversed graph;
• relies on indices, a stack, and low-link values;
• usually harder to understand at first.

Both have linear time complexity.

Common mistakes

• ignoring edge direction;
• using one ordinary DFS and calling the result an SCC;
• forgetting finishing order;
• running the second DFS on the original graph;
• not including vertices with zero outgoing edges;
• confusing SCC detection with cycle detection;
• expecting a fixed component order in the output.

When should you use SCCs?

SCC decomposition is a strong fit when the problem asks questions such as:

• Which vertices can reach each other in both directions?
• Which dependencies form circular groups?
• Which modules or services are tightly coupled?
• How can a directed graph be compressed into a DAG?
• Which states belong to recurrent regions?
• Which parts of a directed network behave as inseparable units?

Summary

Strongly Connected Components partition a directed graph into maximal groups of mutually reachable vertices.

Kosaraju can be remembered as:

DFS finishing order
        ↓
Reverse all edges
        ↓
DFS in reverse finishing order
        ↓
Strongly Connected Components

The deeper idea is not simply to memorize two DFS passes. SCCs give us a way to expose cyclic structure, identify tightly coupled regions, and compress a complicated directed graph into a much simpler DAG.