DSA interview question

Strongly Connected Components (Kosaraju's Algorithm)

Hard · Data structures · Topics: graph, dfs, scc

The problem

A social platform's "follows" graph is directed. A strongly connected component (SCC) is a maximal group of users where everyone can reach everyone else by following links, like a tightly knit community. Find all SCCs. Kosaraju's algorithm uses two DFS passes. The first records vertices by finish time. The second runs on the reversed graph, starting from vertices in decreasing finish time, and each DFS tree of that pass is exactly one SCC.

Example: 5 vertices, edges 1→0, 0→2, 2→1, 0→3, 3→4 → 3 SCCs: {0, 1, 2}, {3}, {4}.

Function signature

vector<vector<int>> kosaraju(int V, const vector<pair<int, int>>& edges);  // each SCC sorted; list sorted

Test cases

Input `(V, edges)`	Output (count, SCCs)	Explanation
`(5, [[1,0],[0,2],[2,1],[0,3],[3,4]])`	`3 [[0, 1, 2], [3], [4]]`
`(6, [[0,1],[1,0],[2,3],[3,2],[1,2],[4,5]])`	`4 [[0, 1], [2, 3], [4], [5]]`	1→2 doesn't merge the pairs
`(3, [[0,1],[1,2],[2,0]])`	`1 [[0, 1, 2]]`	One cycle
`(4, [[0,1],[1,2],[2,3]])`	`4 [[0], [1], [2], [3]]`	A chain: no mutual reachability
`(1, [])`	`1 [[0]]`

(Confirm: edges are directed; a single vertex is its own SCC; the output order is free, and it's sorted here.)

How interviewers phrase it

"Find the number of strongly connected components in a directed graph using Kosaraju's algorithm" (GeeksforGeeks "Strongly Connected Components (Kosaraju's Algo)").

Clarifying questions to ask

The count or the components? (Both are easy; the components are returned here.)
Directed? (Yes. Undirected graphs just have connected components.)
How large? (Up to 10⁵ vertices, so beware recursion depth in C++; iterative DFS may be needed.)

Follow-ups to expect

"Why reverse the graph?"
"Why decreasing finish time?"
"What's the condensation graph?"
"Tarjan's algorithm?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview