Language Selection
Choose your preferred programming language
Showing: Python
Strongly Connected Components
Problem Statement
Given a directed graph, find all strongly connected components (SCCs). A strongly connected component is a maximal set of vertices where there is a path from every vertex to every other vertex in the set.
Input/Output
- Input: A directed graph represented as an adjacency list
- Output: List of strongly connected components (each component is a list of vertices)
Constraints
- 1 ≤ n ≤ 10^4 (number of vertices)
- 0 ≤ edges ≤ 10^4
- Graph may contain self-loops and multiple edges
Examples
Example 1:
Input: n = 5, edges = [[0,1], [1,2], [2,0], [1,3], [3,4]]
Output: [[0,1,2], [3], [4]]
Explanation:
- Vertices 0, 1, 2 form a cycle and are strongly connected
- Vertex 3 is alone
- Vertex 4 is alone
Example 2:
Input: n = 4, edges = [[0,1], [1,2], [2,3], [3,0], [2,0]]
Output: [[0,1,2,3]]
Explanation: All vertices are strongly connected
Example 3:
Input: n = 3, edges = [[0,1], [1,2]]
Output: [[0], [1], [2]]
Explanation: No cycles, each vertex forms its own SCC
Approaches
Approach 1: Kosaraju’s Algorithm
Algorithm:
- Perform DFS on the original graph and store vertices by finish time
- Create a transposed graph (reverse all edges)
- Perform DFS on transposed graph in decreasing order of finish time
- Each DFS tree in step 3 is a strongly connected component
Python:
def findSCCs_Kosaraju(n, edges):
"""
Find strongly connected components using Kosaraju's algorithm
Time: O(V + E)
Space: O(V)
"""
# Build adjacency list
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
# First DFS to get finish times
visited = [False] * n
stack = []
def dfs1(node):
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
dfs1(neighbor)
stack.append(node)
for i in range(n):
if not visited[i]:
dfs1(i)
# Build transposed graph
transposed = [[] for _ in range(n)]
for u, v in edges:
transposed[v].append(u)
# Second DFS on transposed graph
visited = [False] * n
sccs = []
def dfs2(node, component):
visited[node] = True
component.append(node)
for neighbor in transposed[node]:
if not visited[neighbor]:
dfs2(neighbor, component)
while stack:
node = stack.pop()
if not visited[node]:
component = []
dfs2(node, component)
sccs.append(component)
return sccs
Java:
import java.util.*;
class Solution {
/**
* Find strongly connected components using Kosaraju's algorithm
* Time: O(V + E)
* Space: O(V)
*/
public List<List<Integer>> findSCCs_Kosaraju(int n, int[][] edges) {
// Build adjacency list
List<List<Integer>> graph = new ArrayList<>();
List<List<Integer>> transposed = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
transposed.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
transposed.get(edge[1]).add(edge[0]);
}
// First DFS
boolean[] visited = new boolean[n];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs1(i, graph, visited, stack);
}
}
// Second DFS on transposed graph
visited = new boolean[n];
List<List<Integer>> sccs = new ArrayList<>();
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited[node]) {
List<Integer> component = new ArrayList<>();
dfs2(node, transposed, visited, component);
sccs.add(component);
}
}
return sccs;
}
private void dfs1(int node, List<List<Integer>> graph,
boolean[] visited, Stack<Integer> stack) {
visited[node] = true;
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
dfs1(neighbor, graph, visited, stack);
}
}
stack.push(node);
}
private void dfs2(int node, List<List<Integer>> graph,
boolean[] visited, List<Integer> component) {
visited[node] = true;
component.add(node);
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
dfs2(neighbor, graph, visited, component);
}
}
}
}
Go:
// findSCCsKosaraju - Find strongly connected components using Kosaraju's algorithm
// Time: O(V + E)
// Space: O(V)
func findSCCsKosaraju(n int, edges [][]int) [][]int {
// Build adjacency list
graph := make([][]int, n)
transposed := make([][]int, n)
for _, edge := range edges {
u, v := edge[0], edge[1]
graph[u] = append(graph[u], v)
transposed[v] = append(transposed[v], u)
}
// First DFS
visited := make([]bool, n)
stack := []int{}
var dfs1 func(int)
dfs1 = func(node int) {
visited[node] = true
for _, neighbor := range graph[node] {
if !visited[neighbor] {
dfs1(neighbor)
}
}
stack = append(stack, node)
}
for i := 0; i < n; i++ {
if !visited[i] {
dfs1(i)
}
}
// Second DFS on transposed graph
visited = make([]bool, n)
sccs := [][]int{}
var dfs2 func(int, *[]int)
dfs2 = func(node int, component *[]int) {
visited[node] = true
*component = append(*component, node)
for _, neighbor := range transposed[node] {
if !visited[neighbor] {
dfs2(neighbor, component)
}
}
}
for i := len(stack) - 1; i >= 0; i-- {
node := stack[i]
if !visited[node] {
component := []int{}
dfs2(node, &component)
sccs = append(sccs, component)
}
}
return sccs
}
JavaScript:
/**
* Find strongly connected components using Kosaraju's algorithm
* Time: O(V + E)
* Space: O(V)
*/
function findSCCsKosaraju(n, edges) {
// Build adjacency list
const graph = Array(n).fill().map(() => []);
const transposed = Array(n).fill().map(() => []);
for (const [u, v] of edges) {
graph[u].push(v);
transposed[v].push(u);
}
// First DFS
const visited = new Array(n).fill(false);
const stack = [];
function dfs1(node) {
visited[node] = true;
for (const neighbor of graph[node]) {
if (!visited[neighbor]) {
dfs1(neighbor);
}
}
stack.push(node);
}
for (let i = 0; i < n; i++) {
if (!visited[i]) {
dfs1(i);
}
}
// Second DFS on transposed graph
visited.fill(false);
const sccs = [];
function dfs2(node, component) {
visited[node] = true;
component.push(node);
for (const neighbor of transposed[node]) {
if (!visited[neighbor]) {
dfs2(neighbor, component);
}
}
}
while (stack.length > 0) {
const node = stack.pop();
if (!visited[node]) {
const component = [];
dfs2(node, component);
sccs.push(component);
}
}
return sccs;
}
C#:
using System;
using System.Collections.Generic;
public class Solution {
/// <summary>
/// Find strongly connected components using Kosaraju's algorithm
/// Time: O(V + E)
/// Space: O(V)
/// </summary>
public List<List<int>> FindSCCsKosaraju(int n, int[][] edges) {
// Build adjacency list
List<int>[] graph = new List<int>[n];
List<int>[] transposed = new List<int>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
transposed[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
transposed[edge[1]].Add(edge[0]);
}
// First DFS
bool[] visited = new bool[n];
Stack<int> stack = new Stack<int>();
for (int i = 0; i < n; i++) {
if (!visited[i]) {
DFS1(i, graph, visited, stack);
}
}
// Second DFS on transposed graph
visited = new bool[n];
List<List<int>> sccs = new List<List<int>>();
while (stack.Count > 0) {
int node = stack.Pop();
if (!visited[node]) {
List<int> component = new List<int>();
DFS2(node, transposed, visited, component);
sccs.Add(component);
}
}
return sccs;
}
private void DFS1(int node, List<int>[] graph,
bool[] visited, Stack<int> stack) {
visited[node] = true;
foreach (int neighbor in graph[node]) {
if (!visited[neighbor]) {
DFS1(neighbor, graph, visited, stack);
}
}
stack.Push(node);
}
private void DFS2(int node, List<int>[] graph,
bool[] visited, List<int> component) {
visited[node] = true;
component.Add(node);
foreach (int neighbor in graph[node]) {
if (!visited[neighbor]) {
DFS2(neighbor, graph, visited, component);
}
}
}
}
Approach 2: Tarjan’s Algorithm
Algorithm:
- Use DFS with a stack to track the current path
- Assign each node a discovery time and low-link value
- Update low-link values based on back edges
- When a node’s low-link equals its discovery time, pop all nodes from stack until current node (forms an SCC)
Python:
def findSCCs_Tarjan(n, edges):
"""
Find strongly connected components using Tarjan's algorithm
Time: O(V + E)
Space: O(V)
"""
# Build adjacency list
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
disc = [-1] * n
low = [-1] * n
on_stack = [False] * n
stack = []
sccs = []
time = [0] # Use list to make it mutable in nested function
def dfs(node):
disc[node] = low[node] = time[0]
time[0] += 1
stack.append(node)
on_stack[node] = True
for neighbor in graph[node]:
if disc[neighbor] == -1: # Not visited
dfs(neighbor)
low[node] = min(low[node], low[neighbor])
elif on_stack[neighbor]: # Back edge
low[node] = min(low[node], disc[neighbor])
# Found SCC root
if low[node] == disc[node]:
component = []
while True:
v = stack.pop()
on_stack[v] = False
component.append(v)
if v == node:
break
sccs.append(component)
for i in range(n):
if disc[i] == -1:
dfs(i)
return sccs
Java:
class Solution {
private int time = 0;
/**
* Find strongly connected components using Tarjan's algorithm
* Time: O(V + E)
* Space: O(V)
*/
public List<List<Integer>> findSCCs_Tarjan(int n, int[][] edges) {
// Build adjacency list
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
}
int[] disc = new int[n];
int[] low = new int[n];
Arrays.fill(disc, -1);
Arrays.fill(low, -1);
boolean[] onStack = new boolean[n];
Stack<Integer> stack = new Stack<>();
List<List<Integer>> sccs = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (disc[i] == -1) {
tarjanDFS(i, graph, disc, low, onStack, stack, sccs);
}
}
return sccs;
}
private void tarjanDFS(int node, List<List<Integer>> graph,
int[] disc, int[] low, boolean[] onStack,
Stack<Integer> stack, List<List<Integer>> sccs) {
disc[node] = low[node] = time++;
stack.push(node);
onStack[node] = true;
for (int neighbor : graph.get(node)) {
if (disc[neighbor] == -1) {
tarjanDFS(neighbor, graph, disc, low, onStack, stack, sccs);
low[node] = Math.min(low[node], low[neighbor]);
} else if (onStack[neighbor]) {
low[node] = Math.min(low[node], disc[neighbor]);
}
}
if (low[node] == disc[node]) {
List<Integer> component = new ArrayList<>();
while (true) {
int v = stack.pop();
onStack[v] = false;
component.add(v);
if (v == node) break;
}
sccs.add(component);
}
}
}
Go:
// findSCCsTarjan - Find strongly connected components using Tarjan's algorithm
// Time: O(V + E)
// Space: O(V)
func findSCCsTarjan(n int, edges [][]int) [][]int {
// Build adjacency list
graph := make([][]int, n)
for _, edge := range edges {
graph[edge[0]] = append(graph[edge[0]], edge[1])
}
disc := make([]int, n)
low := make([]int, n)
for i := range disc {
disc[i] = -1
low[i] = -1
}
onStack := make([]bool, n)
stack := []int{}
sccs := [][]int{}
time := 0
var dfs func(int)
dfs = func(node int) {
disc[node] = time
low[node] = time
time++
stack = append(stack, node)
onStack[node] = true
for _, neighbor := range graph[node] {
if disc[neighbor] == -1 {
dfs(neighbor)
if low[neighbor] < low[node] {
low[node] = low[neighbor]
}
} else if onStack[neighbor] {
if disc[neighbor] < low[node] {
low[node] = disc[neighbor]
}
}
}
if low[node] == disc[node] {
component := []int{}
for {
v := stack[len(stack)-1]
stack = stack[:len(stack)-1]
onStack[v] = false
component = append(component, v)
if v == node {
break
}
}
sccs = append(sccs, component)
}
}
for i := 0; i < n; i++ {
if disc[i] == -1 {
dfs(i)
}
}
return sccs
}
JavaScript:
/**
* Find strongly connected components using Tarjan's algorithm
* Time: O(V + E)
* Space: O(V)
*/
function findSCCsTarjan(n, edges) {
// Build adjacency list
const graph = Array(n).fill().map(() => []);
for (const [u, v] of edges) {
graph[u].push(v);
}
const disc = new Array(n).fill(-1);
const low = new Array(n).fill(-1);
const onStack = new Array(n).fill(false);
const stack = [];
const sccs = [];
let time = 0;
function dfs(node) {
disc[node] = low[node] = time++;
stack.push(node);
onStack[node] = true;
for (const neighbor of graph[node]) {
if (disc[neighbor] === -1) {
dfs(neighbor);
low[node] = Math.min(low[node], low[neighbor]);
} else if (onStack[neighbor]) {
low[node] = Math.min(low[node], disc[neighbor]);
}
}
if (low[node] === disc[node]) {
const component = [];
let v;
do {
v = stack.pop();
onStack[v] = false;
component.push(v);
} while (v !== node);
sccs.push(component);
}
}
for (let i = 0; i < n; i++) {
if (disc[i] === -1) {
dfs(i);
}
}
return sccs;
}
C#:
public class Solution {
private int time = 0;
/// <summary>
/// Find strongly connected components using Tarjan's algorithm
/// Time: O(V + E)
/// Space: O(V)
/// </summary>
public List<List<int>> FindSCCsTarjan(int n, int[][] edges) {
// Build adjacency list
List<int>[] graph = new List<int>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
}
int[] disc = new int[n];
int[] low = new int[n];
Array.Fill(disc, -1);
Array.Fill(low, -1);
bool[] onStack = new bool[n];
Stack<int> stack = new Stack<int>();
List<List<int>> sccs = new List<List<int>>();
for (int i = 0; i < n; i++) {
if (disc[i] == -1) {
TarjanDFS(i, graph, disc, low, onStack, stack, sccs);
}
}
return sccs;
}
private void TarjanDFS(int node, List<int>[] graph,
int[] disc, int[] low, bool[] onStack,
Stack<int> stack, List<List<int>> sccs) {
disc[node] = low[node] = time++;
stack.Push(node);
onStack[node] = true;
foreach (int neighbor in graph[node]) {
if (disc[neighbor] == -1) {
TarjanDFS(neighbor, graph, disc, low, onStack, stack, sccs);
low[node] = Math.Min(low[node], low[neighbor]);
} else if (onStack[neighbor]) {
low[node] = Math.Min(low[node], disc[neighbor]);
}
}
if (low[node] == disc[node]) {
List<int> component = new List<int>();
int v;
do {
v = stack.Pop();
onStack[v] = false;
component.Add(v);
} while (v != node);
sccs.Add(component);
}
}
}
Complexity Analysis
Kosaraju’s Algorithm:
- Time Complexity: O(V + E) - Two DFS traversals
- Space Complexity: O(V) - For visited arrays and stack
Tarjan’s Algorithm:
- Time Complexity: O(V + E) - Single DFS traversal
- Space Complexity: O(V) - For discovery/low arrays and stack
Key Insights
- Both algorithms use DFS but in different ways
- Kosaraju’s is simpler to understand (two-pass approach)
- Tarjan’s is more efficient (single-pass approach)
- SCCs are fundamental for understanding graph structure
- Useful for circuit analysis, web crawling, and social network analysis
Edge Cases
- Empty graph (no edges)
- Graph with self-loops
- Disconnected components
- Single node forming its own SCC
- Complete graph (all nodes strongly connected)
Common Mistakes
- Forgetting to reverse edges in Kosaraju’s algorithm
- Incorrect low-link value updates in Tarjan’s
- Not handling disconnected components
- Stack management errors in Tarjan’s algorithm
Interview Tips
- Clarify if the graph is directed (SCCs only exist in directed graphs)
- Discuss trade-offs between Kosaraju’s and Tarjan’s algorithms
- Mention real-world applications (e.g., deadlock detection, web crawling)
- Consider mentioning path-based strong component algorithms as alternatives
Follow-up Questions
- How would you find the condensation graph (DAG of SCCs)?
- Can you determine if adding an edge would change the number of SCCs?
- How would you find the largest strongly connected component?
- What if we need to handle dynamic graph updates?
Related Problems
- Critical Connections in a Network
- Articulation Points
- Bridge Finding
- Minimum edges to make graph strongly connected