Groups of Stations That Can All Reach Each Other
Solve this ProblemA 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.
Test Case 1:
Test Case 2:
Test Case 3:
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
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Group Stations That Can Reach Each Other
BruteCompute, for every station, the set of stations it can reach (one depth-first search each). Two stations are in the same group exactly when each reaches the other. Go through the stations in increasing order: for a station that is not yet in a group, collect every station v with reach[u][v] and reach[v][u] into a new group. Groups automatically come out ordered by their smallest station, with increasing members.
O(n · (n + E) + n²)O(n²)1class Solution {
2 private boolean[] reachableFrom(int[][] graph, int start) {
3 boolean[] seen = new boolean[graph.length];
4 Deque<Integer> stack = new ArrayDeque<>();
5 seen[start] = true;
6 stack.push(start);
7 while (!stack.isEmpty()) {
8 int u = stack.pop();
9 for (int v : graph[u]) {
10 if (!seen[v]) {
11 seen[v] = true;
12 stack.push(v);
13 }
14 }
15 }
16 return seen;
17 }
18
19 public List<List<Integer>> strongGroups(int[][] graph) {
20 int n = graph.length;
21 boolean[][] reach = new boolean[n][];
22 for (int s = 0; s < n; s++) reach[s] = reachableFrom(graph, s);
23 boolean[] assigned = new boolean[n];
24 List<List<Integer>> result = new ArrayList<>();
25 for (int u = 0; u < n; u++) {
26 if (assigned[u]) continue;
27 List<Integer> group = new ArrayList<>();
28 for (int v = 0; v < n; v++) {
29 if (reach[u][v] && reach[v][u]) {
30 group.add(v);
31 assigned[v] = true;
32 }
33 }
34 result.add(group);
35 }
36 return result;
37 }
38}Optimal — Kosaraju’s Algorithm
OptimalFirst pass: run a depth-first search over the whole graph and record the stations in the order they FINISH. Then reverse every track. Second pass: take the stations in decreasing finishing order; from each station not yet assigned, run a depth-first search on the reversed graph: everything reached forms one group. The station that finished last lies in a "source" group of the original graph, and in the reversed graph its search cannot leak into other groups. Finally list the groups by their smallest station. Two searches, so O(n + E).
O(n + E)O(n + E)1class Solution {
2 private void firstPass(int[][] graph, int u, boolean[] seen, List<Integer> finished) {
3 seen[u] = true;
4 for (int v : graph[u]) {
5 if (!seen[v]) firstPass(graph, v, seen, finished);
6 }
7 finished.add(u);
8 }
9
10 private void secondPass(List<List<Integer>> reversed, int u, int[] component, int id) {
11 component[u] = id;
12 for (int v : reversed.get(u)) {
13 if (component[v] == -1) secondPass(reversed, v, component, id);
14 }
15 }
16
17 public List<List<Integer>> strongGroups(int[][] graph) {
18 int n = graph.length;
19 boolean[] seen = new boolean[n];
20 List<Integer> finished = new ArrayList<>();
21 for (int start = 0; start < n; start++) {
22 if (!seen[start]) firstPass(graph, start, seen, finished);
23 }
24 List<List<Integer>> reversed = new ArrayList<>();
25 for (int i = 0; i < n; i++) reversed.add(new ArrayList<>());
26 for (int u = 0; u < n; u++) {
27 for (int v : graph[u]) reversed.get(v).add(u);
28 }
29 int[] component = new int[n];
30 Arrays.fill(component, -1);
31 int count = 0;
32 for (int i = n - 1; i >= 0; i--) {
33 int u = finished.get(i);
34 if (component[u] == -1) {
35 secondPass(reversed, u, component, count);
36 count++;
37 }
38 }
39 int[] slot = new int[count];
40 Arrays.fill(slot, -1);
41 List<List<Integer>> result = new ArrayList<>();
42 for (int v = 0; v < n; v++) {
43 if (slot[component[v]] == -1) {
44 slot[component[v]] = result.size();
45 result.add(new ArrayList<>());
46 }
47 result.get(slot[component[v]]).add(v);
48 }
49 return result;
50 }
51}