Log inSign up
hardLeetCodeNot Started

Strongly Connected Components

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

Given a directed graph with V vertices numbered from 0 to V - 1 and E directed edges represented as an adjacency list adj.

A Strongly Connected Component (SCC) is a maximal subset of vertices such that every vertex in the subset is reachable from any other vertex in the subset.

Find the total number of Strongly Connected Components in the graph.

Constraints:

  • 1 <= V <= 5000
  • 0 <= E <= min(V * (V - 1), 105)
  • 0 <= u, v < V
  • No self-loops or multi-edges.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the concept and properties of Strongly Connected Components (SCCs).
  • Implement Kosaraju's 2-pass algorithm with stack finish ordering and edge reversal.
  • Understand the condensed DAG concept and why transposed edges isolate components.
  • Analyze time and space complexity (O(V + E)).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever you need to identify mutually reachable cycles/clusters in a directed graph (or condense a directed graph into a Directed Acyclic Graph - DAG), use Kosaraju's or Tarjan's Strongly Connected Components algorithm.

1. Pairwise Reachability Check (All-Pairs Reachability)

Intuition

Two vertices u and v belong to the same SCC if and only if there is a directed path from u to v AND a directed path from v to u. For every pair of vertices, check mutual reachability using DFS. Group mutually reachable vertices into equivalence classes.

Algorithm

  1. Initialize a 2D boolean reachability matrix canReach[V][V] to false.
  2. For each vertex u from 0 to V - 1:
  3. Run DFS/BFS from u on the graph to populate canReach[u][v] = true for all reachable v.
  4. Initialize visited array of size V with false.
  5. Initialize sccCount = 0.
  6. For i = 0 to V - 1:
  7. If !visited[i]:
  8. sccCount++
  9. For j = 0 to V - 1:
  10. If canReach[i][j] && canReach[j][i]:
  11. visited[j] = true
  12. Return sccCount.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4void dfsReach(int u, int start, const std::vector<std::vector<int>>& adj, std::vector<std::vector<bool>>& reach) {
5 reach[start][u] = true;
6 for (int v : adj[u]) {
7 if (!reach[start][v]) {
8 dfsReach(v, start, adj, reach);
9 }
10 }
11}
12
13int countSCCBrute(int V, const std::vector<std::vector<int>>& adj) {
14 std::vector<std::vector<bool>> reach(V, std::vector<bool>(V, false));
15 for (int i = 0; i < V; ++i) {
16 dfsReach(i, i, adj, reach);
17 }
18
19 std::vector<bool> visited(V, false);
20 int sccCount = 0;
21
22 for (int i = 0; i < V; ++i) {
23 if (!visited[i]) {
24 sccCount++;
25 for (int j = 0; j < V; ++j) {
26 if (reach[i][j] && reach[j][i]) {
27 visited[j] = true;
28 }
29 }
30 }
31 }
32 return sccCount;
33}
34
35int main() {
36 int V = 5;
37 std::vector<std::vector<int>> adj = {{2, 3}, {0}, {1}, {4}, {}};
38 std::cout << "SCC Count (Brute): " << countSCCBrute(V, adj) << std::endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(V * (V + E)) because running DFS from all V vertices takes V * (V + E), followed by V^2 grouping.
  • Space complexity: O(V^2) to store the pairwise reachability matrix.

2. Tarjan's Algorithm (Single Pass DFS)

Intuition

Tarjan's algorithm uses a single DFS traversal to find all SCCs. It maintains discovery times tin[u] and the lowest discovery time reachable via back-edges low[u]. Vertices are pushed onto an auxiliary stack. When low[u] == tin[u], u is the root of an SCC; pop all vertices from the stack up to u to form the SCC.

Algorithm

  1. Initialize tin and low arrays of size V with -1, inStack boolean array with false.
  2. Initialize an auxiliary stack and timer = 0, sccCount = 0.
  3. Define dfs(u):
  4. tin[u] = low[u] = ++timer
  5. Push u to stack, set inStack[u] = true.
  6. For each neighbor v of u:
  7. If tin[v] == -1 (unvisited):
  8. dfs(v)
  9. low[u] = min(low[u], low[v])
  10. Else if inStack[v]:
  11. low[u] = min(low[u], tin[v]) (back edge)
  12. If low[u] == tin[u] (root of an SCC):
  13. sccCount++
  14. Pop elements from stack until u is popped, set inStack = false for each.
  15. Run dfs for all unvisited vertices.
  16. Return sccCount.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4#include <algorithm>
5
6void tarjanDFS(int u, const std::vector<std::vector<int>>& adj, std::vector<int>& tin,
7 std::vector<int>& low, std::vector<bool>& inStack, std::stack<int>& st,
8 int& timer, int& sccCount) {
9 tin[u] = low[u] = ++timer;
10 st.push(u);
11 inStack[u] = true;
12
13 for (int v : adj[u]) {
14 if (tin[v] == -1) {
15 tarjanDFS(v, adj, tin, low, inStack, st, timer, sccCount);
16 low[u] = std::min(low[u], low[v]);
17 } else if (inStack[v]) {
18 low[u] = std::min(low[u], tin[v]);
19 }
20 }
21
22 if (low[u] == tin[u]) {
23 sccCount++;
24 while (true) {
25 int node = st.top();
26 st.pop();
27 inStack[node] = false;
28 if (node == u) break;
29 }
30 }
31}
32
33int countSCCTarjan(int V, const std::vector<std::vector<int>>& adj) {
34 std::vector<int> tin(V, -1), low(V, -1);
35 std::vector<bool> inStack(V, false);
36 std::stack<int> st;
37 int timer = 0, sccCount = 0;
38
39 for (int i = 0; i < V; ++i) {
40 if (tin[i] == -1) {
41 tarjanDFS(i, adj, tin, low, inStack, st, timer, sccCount);
42 }
43 }
44 return sccCount;
45}
46
47int main() {
48 int V = 5;
49 std::vector<std::vector<int>> adj = {{2, 3}, {0}, {1}, {4}, {}};
50 std::cout << "SCC Count (Tarjan): " << countSCCTarjan(V, adj) << std::endl;
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(V + E) single DFS traversal visiting every vertex and edge once.
  • Space complexity: O(V) for the stack, tin, low, and inStack arrays.

3. Kosaraju's 2-Pass DFS Algorithm

Intuition

Run DFS on the original graph, pushing nodes to a stack upon post-order exit. Vertices in source SCCs finish last and will sit at the top of the stack. Next, reverse (transpose) all edges. When we pop nodes from the stack in decreasing finish time and launch DFS on the transposed graph, we cannot leak into downstream SCCs (since inter-SCC edges are reversed). Thus, each DFS traversal on the transposed graph isolates exactly one SCC.

Algorithm

  1. Create visited array of size V with false.
  2. Step 1: Order vertices by finish time using DFS. Push each vertex onto a stack st after exploring all its neighbors.
  3. Step 2: Construct the transposed graph adjT where for each edge u -> v, add v -> u.
  4. Step 3: Reset visited array to false.
  5. Initialize sccCount = 0.
  6. While stack st is not empty:
  7. u = st.top(), pop stack.
  8. If !visited[u]:
  9. sccCount++
  10. Run dfsTranspose(u) on adjT to mark all nodes in this SCC as visited.
  11. Return sccCount.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4
5void dfs1(int u, const std::vector<std::vector<int>>& adj, std::vector<bool>& visited, std::stack<int>& st) {
6 visited[u] = true;
7 for (int v : adj[u]) {
8 if (!visited[v]) {
9 dfs1(v, adj, visited, st);
10 }
11 }
12 st.push(u);
13}
14
15void dfs2(int u, const std::vector<std::vector<int>>& adjT, std::vector<bool>& visited) {
16 visited[u] = true;
17 for (int v : adjT[u]) {
18 if (!visited[v]) {
19 dfs2(v, adjT, visited);
20 }
21 }
22}
23
24int kosarajuSCC(int V, const std::vector<std::vector<int>>& adj) {
25 std::stack<int> st;
26 std::vector<bool> visited(V, false);
27
28 // Step 1: Finish time stack
29 for (int i = 0; i < V; ++i) {
30 if (!visited[i]) {
31 dfs1(i, adj, visited, st);
32 }
33 }
34
35 // Step 2: Transpose graph
36 std::vector<std::vector<int>> adjT(V);
37 for (int u = 0; u < V; ++u) {
38 for (int v : adj[u]) {
39 adjT[v].push_back(u);
40 }
41 }
42
43 // Step 3: DFS on transposed graph in stack order
44 std::fill(visited.begin(), visited.end(), false);
45 int sccCount = 0;
46
47 while (!st.empty()) {
48 int u = st.top();
49 st.pop();
50 if (!visited[u]) {
51 sccCount++;
52 dfs2(u, adjT, visited);
53 }
54 }
55
56 return sccCount;
57}
58
59int main() {
60 int V = 5;
61 std::vector<std::vector<int>> adj = {{2, 3}, {0}, {1}, {4}, {}};
62 std::cout << "Optimal SCC Count (Kosaraju): " << kosarajuSCC(V, adj) << std::endl;
63 return 0;
64}

Time & Space Complexity

  • Time complexity: O(V + E) linear time across 3 passes: first DFS O(V + E), transpose graph O(V + E), second DFS O(V + E).
  • Space complexity: O(V + E) for the transposed adjacency list, recursion stack, and order stack.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Pairwise Reachability CheckO(V * (V + E))O(V^2)Simple brute-force verification.Quadratic memory and cubic worst-case operations on dense graphs.
2.Tarjan's AlgorithmO(V + E)O(V)Single DFS pass; does not require constructing the transposed graph.Requires low and discovery time tracking and careful back-edge conditions.
3.Kosaraju's AlgorithmOptimalO(V + E)O(V + E)Conceptually clean, modular, and very easy to debug and implement.Requires two DFS passes and explicit transposition of graph edges.

Common Pitfalls & Crucial Edge Cases

Pushing nodes to the stack at the start of DFS instead of at the end.

Finish time ordering requires pushing to the stack strictly upon post-order exit after all descendants have been visited.

Forgetting to reset the visited array between Pass 1 and Pass 2.

The visited array must be completely cleared before running DFS on the transposed graph.

Crucial Edge Cases to Validate:

  • DAG with no cycles (e.g. 0 -> 1 -> 2) — Each individual vertex forms its own SCC; returns V.
  • Entire graph is a single huge cycle (0 -> 1 -> ... -> V-1 -> 0) — All vertices belong to the same SCC; returns 1.
  • Disconnected graph with multiple isolated components — Outer loop checks every unvisited vertex; counts each isolated component correctly.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State both major SCC algorithms: Kosaraju's (2-pass with transposition) and Tarjan's (1-pass with low/discovery arrays).
  2. Explain the condensed DAG property clearly: Kosarajus algorithm processes the condensation DAG in reverse topological order.'

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we push nodes onto the stack at the end of the first DFS (post-order exit)?

2.What happens to the internal connectivity of an SCC when all graph edges are transposed?

3.What is the time complexity of Kosaraju's algorithm on a graph with V vertices and E edges?

Back to DSA Sheet