cf.completefrontend
GRAPHS · ADVANCED

Strongly connected components

Split a directed graph into groups where every node can reach every other node in the same group, using two DFS passes.

Time O(n + e)Space O(n + e)2 practice problemsStep-through picture

The idea

In a directed graph, a reaching b doesn't mean b reaches a. A strongly connected component (SCC) is a largest group of nodes where every node can reach every other node in the group by following edges. A loop of modules that import each other is one SCC; a module that nothing imports back is an SCC on its own.

Kosaraju's algorithm finds them with two depth-first searches. The first pass runs DFS on the graph and records the order in which nodes finish. The second pass runs DFS on the reversed graph (every edge flipped), starting from the node that finished last, then the next unclaimed one, and so on. Each DFS in the second pass collects exactly one SCC.

If you shrink each SCC into a single node, the result has no cycles. This shrunk graph, called the condensation, is useful for questions like "how many links must I add so every page can reach every other page?"

An everyday example

One-way streets in a city

A city has only one-way streets. A neighborhood where you can drive from any corner to any other corner and back is a strongly connected part. Between neighborhoods, you might only be able to drive one way: you can get from the old town to the harbor, but not back. Kosaraju first explores the city and notes which areas finish last, then explores again with every street reversed, so each new search stays trapped inside one neighborhood.

How the example maps to the code
In the exampleIn the code
A one-way streetA directed edge [from, to]
Every street driven backwardsThe reverse graph
The order areas were fully exploredThe finished list
One neighborhoodNodes with the same component number
Counting neighborhoodscount

From the slow way to strongly connected components

  1. Start with the obvious way: from every node, run a DFS to list everything it can reach. Two nodes are in the same group when each one reaches the other. That's n searches, O(n · (n + e)) steps, plus an n by n table: about 600 million steps for 10,000 nodes and 50,000 edges.
  2. A smaller idea: a search from u finds everything u reaches, and a search from u over the reversed edges finds everything that reaches u. The nodes found by both searches are exactly u's group. That's two searches per group instead of one per node, but you still have to compare the two results.
  3. Now suppose u's group is a source group: no edge from another group points into it. Then in the reversed graph, no edge leads out of the group, so a single reversed search from u finds exactly the group and nothing else. Label it, set it aside, and the remaining graph has a new source group to start from.
  4. How do we find a node in a source group, then the next one? One ordinary DFS gives each node a finish time. If any edge goes from group C to group D, some node of C finishes after every node of D. So the node that finishes last is in a source group, and walking the finish order backwards meets the groups source-first. One DFS for the order, then reversed searches in that order: that is Kosaraju's algorithm.

How it works

  1. Build graph and also reverse, which has every edge flipped.
  2. First pass: run DFS on graph from every unvisited node. When a node finishes, push it onto finished.
  3. Second pass: go through finished from the end (the last node to finish) to the start.
  4. For each node that has no component yet, run DFS on reverse, giving every node it reaches the number count.
  5. Add one to count after each second-pass DFS.
  6. Return component, where component[node] tells which SCC each node belongs to.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function stronglyConnected(n, edges) {
  2. const graph = Array.from({ length: n }, () => []);
  3. const reverse = Array.from({ length: n }, () => []);
  4. for (const [from, to] of edges) {
  5. graph[from].push(to);
  6. reverse[to].push(from);
  7. }
  8. const visited = new Array(n).fill(false);
  9. const finished = [];
  10. function forward(node) {
  11. visited[node] = true;
  12. for (const next of graph[node]) if (!visited[next]) forward(next);
  13. finished.push(node);
  14. }
  15. for (let node = 0; node < n; node++) if (!visited[node]) forward(node);
  16. const component = new Array(n).fill(-1);
  17. let count = 0;
  18. function backward(node) {
  19. component[node] = count;
  20. for (const prev of reverse[node]) if (component[prev] === -1) backward(prev);
  21. }
  22. for (let i = n - 1; i >= 0; i--) {
  23. const node = finished[i];
  24. if (component[node] === -1) {
  25. backward(node);
  26. count++;
  27. }
  28. }
  29. return component;
  30. }

How fast it is

TimeO(n + e)
Extra memoryO(n + e)

Two DFS passes each touch every node and edge once. The reversed graph doubles the stored edges, which is still O(n + e).

  • Best caseO(n + e)

    Every input. Even a graph with no edges runs n tiny searches in each pass.

  • Average caseO(n + e)

    Every input: building graph and reverse reads each edge once, and each pass follows each edge once.

  • Worst caseO(n + e)

    Every input. A long chain is the same speed but makes the recursion as deep as the chain, which can overflow the call stack.

Common mistakes

  • Running the second pass on the original graph instead of the reversed one. A search then spills into other groups.
  • Going through finished from the start instead of the end.
  • Using an undirected graph. Strongly connected only makes sense when edges have a direction; for undirected graphs, use plain connected components.
  • Overflowing the call stack on long chains. For huge graphs, write both passes with explicit stacks.

When to use it

Look for these clues in a problem:

  • The graph is directed and the question asks which nodes can all reach each other.
  • You need to group nodes that are in loops together, such as circular imports.
  • The question asks how many edges to add so every node can reach every other.
  • You want to turn a directed graph with cycles into one without cycles before doing more work.

Check yourself

Answer each one in your head first, then open it.

Why must the second pass use the reversed graph?

On the original edges, a search from a source group would follow its outgoing edges into other groups. Reversed, those edges point in, so the search stays inside.

What happens if the second pass goes through finished from the start instead of the end?

It starts in a sink group first. On reversed edges, a sink group's incoming edges become outgoing, so the search spills into the groups that point to it and merges them wrongly.

In the trace, why did node 1 finish last even though node 0's search ran first?

Node 0's search couldn't reach node 1, so node 1 started its own search after everything else had finished.

If the edge 6 → 3 is added to the trace's graph, how many groups are there?

One. Node 6 now reaches 3, then 1 and 2, and from there 4 and 0, while 0 already reached 6, so all 7 nodes reach each other.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The key fact: if some edge goes from group C to a different group D, then the latest finish time in C is later than every finish time in D. If the first pass enters C first, at node x, it reaches all of D through that edge before x finishes. If it enters D first, it can't reach C from there, because then C and D would be one group, so all of D finishes before C is even entered.

The second pass keeps this rule: when backward(node) starts at the unlabeled node that finished latest, no unlabeled group has an edge into node's group. Any such group would have a later finish, by the key fact, and would have been labeled first. In the reversed graph, the edges leading out of the group are exactly the edges that came into it, and those all come from labeled groups. So the search stays inside the group, and it reaches all of it, because every node of a group can reach every other node, with edges reversed too.

Each node is labeled exactly once, and each search labels exactly one whole group, so count ends as the number of groups and component names each node's group. Both passes visit every node once and look at every edge once, so the work always ends.

Going deeper

3 more ideas

Why the reversed graph keeps each search inside one group

The node that finishes last in the first pass belongs to a "source" group: no other group has edges into it. In the reversed graph, edges out of that group are all flipped to point in, so a DFS from it can only reach nodes of its own group. After those are claimed, the next unclaimed node in finish order is in the next source group among the rest, and the same reasoning repeats.

Cost

Each pass visits every node once and follows every edge once, and building the reversed graph is one more pass over the edges. The total is O(n + e).

Tarjan's algorithm

Tarjan's algorithm finds the same groups in one DFS by tracking each node's discovery time and the lowest discovery time it can reach (its low-link), using a stack of nodes on the current search. It's faster in practice but harder to get right. Both give the same groups.

Work it by hand

Every step in a table, with why

Seven nodes in three groups: two loops and a pair, joined by one-way edges. The node that finishes last is found late but still starts the second pass.

n = 7, edges = [[0,2], [2,4], [4,0], [4,5], [5,6], [6,5], [1,3], [3,1], [3,2]]

StepPassStepfinished or componentWhat happensWhy
11forward(0)finished = []Visit 0, 2, 4, 5, 6The search follows 0 → 2 → 4. Node 4's first edge goes back to 0, already visited, so it moves on to 5 and then 6.
216, 5, 4, 2, 0 finish[6, 5, 4, 2, 0]Push on the way backNode 6's only edge leads back to 5, which is visited, so 6 finishes first. Then each caller finishes in turn.
31forward(1)[6, 5, 4, 2, 0]Visit 1, 3Node 1 is the next unvisited node. Node 3's edges lead to 1 and 2, both already visited.
413, 1 finish[6, 5, 4, 2, 0, 3, 1]First pass doneNode 1 finishes last, even though it was found last. Nothing points into its group from outside.
52backward(1)[-1, 0, -1, 0, -1, -1, -1]Group 0: {1, 3}Reversed, node 1 is reached only from 3, and 3 only from 1. The edge 3 → 2 points out of this group, so the reversed search can't follow it from here.
623unchangedSkip: labeledNode 3 already has a group.
72backward(0)[1, 0, 1, 0, 1, -1, -1]Group 1: {0, 2, 4}Reversed edges lead from 0 to 4, then 2, then back to 0. Node 2 is also reached from 3, but 3 is already in group 0, so the search stops there.
822, 4unchangedSkip: labeledBoth were labeled in the last search.
92backward(5)[1, 0, 1, 0, 1, 2, 2]Group 2: {5, 6}Node 5 is reached from 4 and 6. Node 4 is labeled, so only 6 joins.
1026unchangedSkip; count = 3Every node is labeled, and three searches ran in the second pass.

It returns component = [1, 0, 1, 0, 1, 2, 2]: groups {1, 3}, {0, 2, 4}, and {5, 6}. The numbers follow the edges between groups: 3 → 2 goes from group 0 to group 1, and 4 → 5 from group 1 to group 2.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Strongly connected componentsO(n + e)O(n + e)You need every group of a directed graph, and building a reversed copy is fine.
Tarjan's algorithmO(n + e)O(n + e)You want one pass and no reversed graph, and you're comfortable with low-links and the extra stack.
Search from every nodeO(n^2 + n · e)O(n^2)The graph is tiny, or you need the full "who reaches whom" table anyway.

Extra memory: O(n + e): graph and reverse each hold every edge, visited, finished, and component hold n entries, and the recursion can go n calls deep.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Strongly connected components and the other approaches, on a scale where each line up is 10 times more steps.
  • Strongly connected components, Tarjan's algorithm O(n + e)
  • Search from every node O(n^2 + n · e)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Strongly connected components202,0002 million
Tarjan's algorithm202,0002 million
Search from every node2002 million2 trillion

Inputs that need care

5 tricky inputs
No edges: n = 4, edges = []
Every node is its own group. It returns [3, 2, 1, 0], because the node that finished last, 3, is labeled first.
No loops at all: edges 2 → 0, 0 → 3, 3 → 1
Every node is alone, and the numbers come out in a valid dependency order: [1, 3, 0, 2] puts 2 first and 1 last.
A self-loop, like 1 → 1 inside the loop 0 → 1 → 2 → 0
It changes nothing: all three nodes are group 0. A node with only a self-loop is still a group of one, so check self-loops separately if they count as loops for your question.
One big loop through every node
The first reversed search reaches everything, so count is 1 and every component is 0.
A chain of 200,000 nodes
The recursive forward throws "Maximum call stack size exceeded". Rewrite both passes with an explicit stack for graphs that deep.

Variations and follow-ups

Twists interviewers add

Tarjan's algorithm

One DFS instead of two. Each node gets a discovery time and a low-link, the earliest discovery time reachable from its subtree while staying on a stack of open nodes. When a node's low-link equals its own discovery time, everything above it on the stack is one group. It skips building reverse, and groups come out sink-first.

The condensation

Shrink each group to one node by adding an edge component[a] → component[b] for every original edge between different groups. The result has no loops, so you can topologically sort it or run dynamic programming on it, like finding the most nodes collectable on one walk.

Edges needed to connect everything

To make every node reach every other node, count the groups with no incoming edges (sources) and with no outgoing edges (sinks) in the condensation. The answer is the larger of the two, or 0 when there's only one group.

2-SAT

A list of rules like "a or not b" becomes implication edges such as "not a → not b". The rules can all be true exactly when no variable shares a group with its own opposite.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from a directed graph plus "reach each other", "mutually reachable", "circular dependencies", or "groups that form loops". If the edges have no direction, say so and use plain connected components instead.
  • Explain the two passes in two sentences: "the first DFS's finish order puts source groups last; the second DFS, on reversed edges in reverse finish order, can't leak out of a source group".
  • Test by hand a graph with a one-way edge between two loops, like 3 → 2 in the trace, and check that the second pass doesn't merge the two loops.
  • Expect "can you do it in one pass?". Answer: Tarjan's algorithm, with discovery times and low-links, in the same O(n + e).

Where frontend code uses it

The same idea in real UI code
  • Bundlers and linters that report circular dependency groups: every SCC with more than one module is a set of files that import each other in a loop.
  • Reactive state libraries and spreadsheet engines that need to find groups of values that depend on each other before they can order updates.
  • Site-map and SEO tools that group pages that link to each other in loops and find pages that can't be reached back.

Related algorithms