Groups of Stations That Can All Reach Each Other
Implement strongGroups
A rail network has one-way tracks between stations (a directed graph as an adjacency list). Two stations are in the same group when you can travel from each one to the other. Find all such groups (the strongly connected components).
Kosaraju's algorithm needs just two depth-first searches: one on the original graph to record the finishing order, and one on the reversed graph, started in decreasing finishing order, to collect the groups.
Example 1:
Input: graph = [[1],[2],[0,3],[4],[5],[3,6],[7],[]]
Output: [[0,1,2],[3,4,5],[6],[7]]
Example 2:
Input: graph = [[1],[]]
Output: [[0],[1]]
Example 3:
Input: graph = [[1],[2],[0]]
Output: [[0,1,2]]
+ 15 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 8 stations numbered 0 … n-1; graph[u] lists, in increasing order, every station v that has a one-way track u → v (adjacency-list form of a directed graph) - ●
Two stations belong to the same group when each can be reached from the other by following the tracks; a station always belongs to its own group - ●
Every station belongs to exactly one group; a station that lies on no circuit forms a group of its own - ●
Return the groups, each as an increasing list of stations, ordered by their smallest station
graph =
[[1], [2], [0,3], [4], [5], [3,6], [7], []]