Problem
Practice version: partition a directed graph into maximal groups where every node can reach every other node. The report identifies an SCC-related round but does not disclose its complete statement.
Worked examples
Input: edges = [(0,1),(1,0),(1,2)]
Output: {0,1}, {2}
0 and 1 reach each other; 2 cannot reach either.
Hints
Hint 1
Run depth-first search and record finishing order.
Hint 2
Reverse every directed edge for a second pass.
Solution approach
- In Kosaraju’s algorithm, traverse the original graph to collect vertices in finishing order.
- Build the reversed graph and traverse vertices in reverse finishing order. Each new traversal forms one component.
- Use an explicit stack for deep graphs to avoid recursion limits. Explain why finishing order prevents components from merging.
Complexity
O(V + E) time and O(V + E) space.
Report & practice notes
Reported topic only. This standard SCC exercise is an original practice reconstruction, not the exact undisclosed interview prompt.
Read the candidate’s source report ↗