GraphProblem 27 of 43
Count Strongly connected Components (Kosaraju Algo)
Problem Statement
Given a directed graph, count the number of Strongly Connected Components (SCCs). A strongly connected component is a maximal set of vertices such that there is a path from every vertex to every other vertex in the set.
Example:
- Input:
V = 5, edges = [(0,2), (2,1), (1,0), (0,3), (3,4)] - Output:
3(SCCs: 2, 3, 4)
Noob-Friendly Explanation
Think of a city with one-way streets. A Strongly Connected Component is a neighbourhood where you can reach any house from any other house using those one-way streets. You might need to take a roundabout route, but you can always get there.
For example, if houses A, B, C can all reach each other through one-way streets, they form one SCC. But if house D can be reached from A but there's no way back, D is in a different SCC.
Kosaraju's algorithm finds all such neighbourhoods by doing two passes of DFS — one on the original graph and one on the reversed graph.
Approach 1: Brute Force
Intuition
For each pair of vertices (u, v), check if u can reach v AND v can reach u. Group vertices that are mutually reachable into the same SCC.
Algorithm
- For each vertex, run BFS/DFS to find all vertices reachable from it.
- Two vertices are in the same SCC if each can reach the other.
- Use a visited set to avoid counting the same SCC twice.
java
import java.util.*;
public class SCCBruteForce {
public static int countSCCs(int V, List<List<Integer>> adj) {
// For each node, find all reachable nodes
boolean[][] reachable = new boolean[V][V];
for (int i = 0; i < V; i++) {
bfs(i, adj, reachable[i], V);
}
// Group mutually reachable nodes
boolean[] assigned = new boolean[V];
int sccCount = 0;
for (int i = 0; i < V; i++) {
if (assigned[i]) continue;
sccCount++;
assigned[i] = true;
for (int j = i + 1; j < V; j++) {
if (!assigned[j] && reachable[i][j] && reachable[j][i]) {
assigned[j] = true;
}
}
}
return sccCount;
}
static void bfs(int src, List<List<Integer>> adj, boolean[] reach, int V) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(src);
reach[src] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int neigh : adj.get(node)) {
if (!reach[neigh]) {
reach[neigh] = true;
queue.offer(neigh);
}
}
}
}
public static void main(String[] args) {
int V = 5;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
adj.get(0).add(2);
adj.get(2).add(1);
adj.get(1).add(0);
adj.get(0).add(3);
adj.get(3).add(4);
System.out.println("Number of SCCs: " + countSCCs(V, adj));
}
}Complexity Analysis
- Time Complexity: O(V * (V + E)) - BFS/DFS from each vertex
- Space Complexity: O(V + E) - adjacency list plus the reachability matrix O(V²)
Approach 2: Optimal (Kosaraju's Algorithm)
Intuition
Kosaraju's algorithm uses two DFS passes:
- First DFS on the original graph to get the finish order (similar to topological sort).
- Reverse all edges.
- Second DFS on the reversed graph, processing vertices in reverse finish order. Each DFS tree in the second pass is one SCC.
Algorithm
- Run DFS on the original graph. Push vertices onto a stack in order of finish time.
- Create the transpose (reversed) graph.
- Pop vertices from the stack. For each unvisited vertex, run DFS on the transpose. All vertices visited in this DFS form one SCC.
java
import java.util.*;
public class KosarajuSCC {
public static int countSCCs(int V, List<List<Integer>> adj) {
// Step 1: Fill the stack with finish order
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < V; i++) {
if (!visited[i]) {
dfs1(i, adj, visited, stack);
}
}
// Step 2: Create transpose graph
List<List<Integer>> transpose = new ArrayList<>();
for (int i = 0; i < V; i++) transpose.add(new ArrayList<>());
for (int u = 0; u < V; u++) {
for (int v : adj.get(u)) {
transpose.get(v).add(u);
}
}
// Step 3: Process in reverse finish order
Arrays.fill(visited, false);
int sccCount = 0;
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited[node]) {
dfs2(node, transpose, visited);
sccCount++;
}
}
return sccCount;
}
static void dfs1(int u, List<List<Integer>> adj, boolean[] visited, Stack<Integer> stack) {
visited[u] = true;
for (int v : adj.get(u)) {
if (!visited[v]) {
dfs1(v, adj, visited, stack);
}
}
stack.push(u);
}
static void dfs2(int u, List<List<Integer>> transpose, boolean[] visited) {
visited[u] = true;
for (int v : transpose.get(u)) {
if (!visited[v]) {
dfs2(v, transpose, visited);
}
}
}
public static void main(String[] args) {
int V = 5;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
adj.get(0).add(2);
adj.get(2).add(1);
adj.get(1).add(0);
adj.get(0).add(3);
adj.get(3).add(4);
System.out.println("Number of SCCs: " + countSCCs(V, adj));
}
}Complexity Analysis
- Time Complexity: O(V + E) - two DFS traversals, each O(V + E)
- Space Complexity: O(V + E) - for both adjacency lists and the stack