PROBLEM DESCRIPTION
Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, Find the number of strongly connected components in the graph.
SOLUTION
Good Explanation - takeUForward
- We want to find the strongly connected components (SCCs) in a directed graph, where each SCC is a group of nodes where every node can reach every other node.
- First, we perform a DFS on the graph and store the nodes in a stack based on their finish time (when all neighbors are visited).
- Then, we reverse the graph by reversing the direction of all edges.
- After that, we perform DFS again on the reversed graph, using the nodes in the order stored in the stack.
- Each DFS on the reversed graph identifies a new strongly connected component (SCC).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class Solution {
public int kosaraju(int V, ArrayList<ArrayList<Integer>> adj) {
// Stack to store vertices based on their finishing time in the first DFS
Stack<Integer> stack = new Stack<>();
boolean[] visited = new boolean[V];
// Perform DFS on each vertex
for (int i = 0; i < V; i++) {
if (!visited[i])
dfs1(V, adj, stack, i, visited);
}
// Reverse the edges of the graph (transpose of the graph)
ArrayList<ArrayList<Integer>> adjReversed = new ArrayList<>();
for (int i = 0; i < V; i++)
adjReversed.add(new ArrayList<Integer>());
// Reverse all edges in the adjacency list
for (int i = 0; i < V; i++) {
for (Integer j : adj.get(i)) {
// Reverse edge direction
adjReversed.get(j).add(i);
}
}
// Initialize visited array again for the second DFS on the reversed graph
int count = 0;
visited = new boolean[V];
// Process all nodes in the order of their finish time (from the stack)
while (!stack.isEmpty()) {
// Get the next node based on finish time
int node = stack.pop();
// Perform DFS on the reversed graph if the node is not yet visited
if (!visited[node]) {
// Each DFS call in the reversed graph represents a new SCC
count++;
dfs2(V, adjReversed, node, visited);
}
}
return count;
}
// First DFS function to record the finishing order of nodes
public void dfs1(int V, ArrayList<ArrayList<Integer>> adj, Stack<Integer> stack, int node, boolean[] visited) {
// Base case: return if the node is already visited
if (visited[node])
return;
// Mark the current node as visited
visited[node] = true;
// Recursively call DFS for all adjacent nodes
for (Integer n : adj.get(node)) {
dfs1(V, adj, stack, n, visited);
}
// After visiting all neighbors, push the current node onto the stack
stack.push(node);
}
// Second DFS function on the reversed graph to identify SCCs
public void dfs2(int V, ArrayList<ArrayList<Integer>> adj, int node, boolean[] visited) {
// Base case: return if the node is already visited
if (visited[node])
return;
// Mark the current node as visited
visited[node] = true;
// Recursively call DFS for all adjacent nodes in the reversed graph
for (Integer n : adj.get(node)) {
dfs2(V, adj, n, visited);
}
}
}