Stations From Which You Can Never Get Trapped
Solve this ProblemA rail network has n stations connected by one-way tracks, given as an adjacency list of a directed graph. A terminal station has no outgoing track. A station is safe when every possible route that starts there is guaranteed to reach a terminal station; if some route can circle forever, the station is unsafe. List all safe stations in increasing order.
Unsafe stations are exactly those that can reach a circuit, so a depth-first search that remembers which stations are on the current path can label them all in one pass.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 10 stations numbered 0 … n-1; graph[u] lists, in increasing order, every station v reachable from u by a one-way track (adjacency-list form of a directed graph) - ◆
A terminal station has no outgoing track; a station may also have a track to itself - ◆
A station is safe when EVERY route that starts there ends at a terminal station after finitely many steps (no route can circle forever) - ◆
Return all safe stations in increasing order (an empty list if there are none)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Check Every Reachable Station for a Circuit
BruteA station is unsafe exactly when it can reach a station that lies on a circuit (a route that returns to itself); from there a route can circle forever. So for every station, collect all stations reachable from it (including itself) and, for each of them, run a search to see whether it can return to itself. If none of them can, the station is safe. Up to n stations, n candidates each, one O(n + E) search per candidate.
O(n² · (n + E))O(n)1class Solution {
2 private boolean canReturn(int[][] graph, int start) {
3 boolean[] seen = new boolean[graph.length];
4 Deque<Integer> stack = new ArrayDeque<>();
5 for (int v : graph[start]) {
6 if (!seen[v]) {
7 seen[v] = true;
8 stack.push(v);
9 }
10 }
11 while (!stack.isEmpty()) {
12 int u = stack.pop();
13 if (u == start) return true;
14 for (int w : graph[u]) {
15 if (!seen[w]) {
16 seen[w] = true;
17 stack.push(w);
18 }
19 }
20 }
21 return false;
22 }
23
24 private boolean reachesCircuit(int[][] graph, int start) {
25 boolean[] seen = new boolean[graph.length];
26 Deque<Integer> stack = new ArrayDeque<>();
27 seen[start] = true;
28 stack.push(start);
29 while (!stack.isEmpty()) {
30 int u = stack.pop();
31 if (canReturn(graph, u)) return true;
32 for (int w : graph[u]) {
33 if (!seen[w]) {
34 seen[w] = true;
35 stack.push(w);
36 }
37 }
38 }
39 return false;
40 }
41
42 public int[] safeStations(int[][] graph) {
43 List<Integer> safe = new ArrayList<>();
44 for (int u = 0; u < graph.length; u++) {
45 if (!reachesCircuit(graph, u)) safe.add(u);
46 }
47 int[] answer = new int[safe.size()];
48 for (int i = 0; i < answer.length; i++) answer[i] = safe.get(i);
49 return answer;
50 }
51}Optimal — One Depth-First Search With Three States
OptimalExplore with a depth-first search that marks each station 1 while it is on the current path. If a track leads to a station in state 1, a circuit has been found: the search stops going deeper, and the stations on the path stay marked 1, meaning "unsafe". A station whose tracks all lead to safe stations finishes with state 2 (safe). Because states are never reset, every station and track is handled once. The answer is the stations in state 2, in increasing order: O(n + E).
O(n + E)O(n)1class Solution {
2 private boolean explore(int[][] graph, int node, int[] state) {
3 state[node] = 1;
4 for (int next : graph[node]) {
5 if (state[next] == 1) return true;
6 if (state[next] == 0 && explore(graph, next, state)) return true;
7 }
8 state[node] = 2;
9 return false;
10 }
11
12 public int[] safeStations(int[][] graph) {
13 int n = graph.length;
14 int[] state = new int[n];
15 for (int start = 0; start < n; start++) {
16 if (state[start] == 0) explore(graph, start, state);
17 }
18 List<Integer> safe = new ArrayList<>();
19 for (int i = 0; i < n; i++) {
20 if (state[i] == 2) safe.add(i);
21 }
22 int[] answer = new int[safe.size()];
23 for (int i = 0; i < answer.length; i++) answer[i] = safe.get(i);
24 return answer;
25 }
26}