Given a directed graph with V vertices numbered from 0 to V - 1 and a list of directed edges, find the number of strongly connected components using Kosaraju's algorithm.
A strongly connected component is a maximal group of vertices where every vertex can reach every other vertex through directed paths. Every edge is represented as [source, destination].
Example 1
Input: V = 5, edges = [[1,0],[0,2],[2,1],[0,3],[3,4]]
Output: 3
Explanation: The strongly connected components are {0,1,2}, {3}, and {4}.
Example 2
Input: V = 4, edges = [[0,1],[1,2],[2,3],[3,0]]
Output: 1
Explanation: Every vertex reaches every other vertex through the directed cycle, so all four vertices form one strongly connected component.
Approach
The first DFS pass records vertices only after every outgoing path finishes. Reversing the resulting finish order places a vertex from a source component of the remaining condensation graph first.
Reversing every graph edge preserves each SCC internally while reversing all connections between different SCCs. A DFS from the next highest-finish vertex on the transpose therefore remains inside exactly one unvisited SCC. Prerequisite concepts include directed DFS, finish times, graph transposition, stacks, and condensation graphs.
Algorithm
Build both the original graph and its transpose so the same vertices can be explored in opposite edge directions.
Run DFS on the original graph because finishing a vertex after all its outgoing paths captures the required finish-time ordering.
Add each vertex to the finish-order list only after its DFS completes, so vertices with later finishing times appear toward the end.
Reset the visited array after the first DFS pass because the second pass must identify SCCs independently.
Traverse the finish-order list from right to left so vertices with the highest finishing times are processed first.
Start DFS on the transpose graph whenever an unvisited vertex is found because all vertices reached in this traversal belong to the same SCC.
Mark every reached vertex as visited so the same SCC is not counted again.
Increment the SCC count once for each new DFS traversal on the transpose graph.
Return the final SCC count after all vertices have been processed.
Dry Run
kosaraju
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Function to record vertices after complete DFS exploration. void recordFinishOrder(int start, const vector<vector<int>>& adjacency, vector<bool>& visited, vector<int>& finishOrder) { // Store {vertex, next neighbor index} as an explicit DFS frame. stack<pair<int, int>> frames; frames.push({start, 0}); visited[start] = true; while (!frames.empty()) { int node = frames.top().first; int& nextIndex = frames.top().second; // Explore the next unvisited outgoing neighbor. if (nextIndex < static_cast<int>(adjacency[node].size())) { int neighbor = adjacency[node][nextIndex++]; if (!visited[neighbor]) { visited[neighbor] = true; frames.push({neighbor, 0}); } continue; } // Record the vertex only after every neighbor finishes. finishOrder.push_back(node); frames.pop(); } } // Function to mark one SCC in the transpose graph. void markComponent(int start, const vector<vector<int>>& transpose, vector<bool>& visited) { stack<int> pending; pending.push(start); visited[start] = true; while (!pending.empty()) { int node = pending.top(); pending.pop(); // Traverse every reversed edge inside the current SCC. for (int neighbor : transpose[node]) { if (!visited[neighbor]) { visited[neighbor] = true; pending.push(neighbor); } } } }public: // Function to count strongly connected components with Kosaraju's algorithm. int kosaraju(int vertices, vector<vector<int>>& edges) { vector<vector<int>> adjacency(vertices); vector<vector<int>> transpose(vertices); // Build both the original graph and the edge-reversed graph. for (const auto& edge : edges) { adjacency[edge[0]].push_back(edge[1]); transpose[edge[1]].push_back(edge[0]); } vector<bool> visited(vertices, false); vector<int> finishOrder; // Cover every DFS tree in the original directed graph. for (int node = 0; node < vertices; node++) { if (!visited[node]) { recordFinishOrder(node, adjacency, visited, finishOrder); } } fill(visited.begin(), visited.end(), false); int componentCount = 0; // Process vertices from largest finish time to smallest. for (int index = vertices - 1; index >= 0; index--) { int node = finishOrder[index]; if (!visited[node]) { componentCount++; markComponent(node, transpose, visited); } } // Return the number of strongly connected components. return componentCount; }};// Driver function with a hard-coded directed graph.int main() { int vertices = 5; vector<vector<int>> edges = { {1, 0}, {0, 2}, {2, 1}, {0, 3}, {3, 4} }; Solution solution; cout << solution.kosaraju(vertices, edges) << "\n"; return 0;}Complexity Analysis
Time Complexity: O(V+E), graph construction and both DFS passes process every vertex and edge a constant number of times. Here, V is the number of vertices and E is the number of directed edges in the graph.
Space Complexity: O(V+E), adjacency lists, transpose lists, visited markers, finish order, and DFS stacks store graph state. Here, V is the number of vertices and E is the number of directed edges in the graph.
Interview follow-up Questions
Kosaraju's algorithm targets directed graphs. Connected components already capture mutual reachability in an undirected graph.
Be the first to add a comment.