DSA-106 · Peel terminals backward only when every outgoing successor is certified safe
Eventual Safe States
Core · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 134151 deterministic checks. Learner drafts are not executed.
Understand the problem
Return every vertex from which every possible directed path eventually terminates. Return labels in ascending order.
- graph is a nonnull adjacency-list array with nonnull rows and vertex labels 0..graph.length-1. Empty graphs and rows are valid. At most 100,000 vertices and 200,000 outgoing occurrences are size preconditions. Null outer input throws NullPointerException; null rows and invalid endpoints throw IllegalArgumentException before traversal.
- Edges are directed and may include self-loops, cycles, duplicate occurrences, disconnected components, and shared read-only adjacency rows. A terminal has no outgoing occurrences. A vertex is safe only when every possible continuation terminates; reaching one terminal along one branch is insufficient.
- Preserve every input value and row reference. Return a fresh mutable List<Integer> in ascending label order, independent across calls. The internal reverse-removal sequence is not the output ordering, and a residual vertex can feed a cycle without being on it.
Examples
Input:
[[1,2],[2,3],[5],[0],[5],[],[]]
Output:[2,4,5,6]The cycle 0→1→3→0 makes those vertices unsafe, even though 1 can also reach terminal 5 via 2.
Input:
[[1,2],[],[2]]
Output:[1]Vertex 0 can choose the terminal branch, but can also enter the self-loop at 2; safety quantifies over every path.
Input:
[[1,1],[],[2]]
Output:[0,1]Both duplicate occurrences from 0 are discharged when terminal 1 is removed; self-loop 2 remains blocked.
Before you start
- Universal path safety versus ordinary reachability
- Reverse adjacency and outgoing occurrence counts
Recognize the structure
This is not ordinary reverse BFS from terminal nodes: that would prove existence of a terminating path. Universal safety requires every outgoing obligation to be discharged. Reverse topological elimination starts with terminals and admits a predecessor only when no uncertified successor occurrences remain.
Try before revealing
Hint 1
A terminal is safe without choosing an outgoing edge.
Hint 2
A predecessor becomes safe only after every successor is safe.
Hint 3
Count remaining outgoing occurrences, peel via reverse edges, and collect labels in sorted order.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Compute transitive reachability and reject every cycle predecessor
Build a boolean reachability matrix from actual edges, without initially setting every diagonal true. Floyd-style closure makes reach[c][c] true exactly for vertices on a nonempty directed cycle. Vertex v is unsafe if it is on such a cycle or reaches one. This compiling baseline is cubic and uses quadratic memory, so it is restricted to small verification graphs.
Improve the baseline
Count successors, not incoming prerequisites
remaining[v] starts at graph[v].length. Build reverse[next] with one predecessor occurrence for each original edge. This reverses propagation while preserving multiplicity.
Start from universally terminating base cases
Seed terminals with zero remaining count. Removing a safe vertex discharges its incoming predecessor obligations. Only a predecessor reaching exactly zero can be scheduled.
Separate certification history from returned ordering
Record safety on removal, then scan labels 0..n-1 to build the sorted mutable result. Never sort or overwrite caller adjacency rows.
Why it is correct
Every certified vertex is safe
Terminals terminate immediately. When a new vertex is removed, every one of its successors has already been certified safe. Every possible first step therefore enters a terminating continuation, proving universal safety inductively.
Every safe vertex is eventually certified
In a finite graph, a safe vertex cannot reach a cycle. Its reachable subgraph is a DAG; repeatedly removing sinks eliminates all of it. Hence its outgoing obligations eventually reach zero and it is processed.
Residual vertices are precisely unsafe
At exhaustion each residual vertex has a residual outgoing edge. Following these edges forever in a finite graph reaches a cycle, giving at least one nonterminating continuation. Unsafe vertices may be on the cycle or merely able to reach it.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.*;
public final class Solution {
private static void validate(int[][] graph) {
Objects.requireNonNull(graph,"graph");for(int[] row:graph){if(row==null)throw new IllegalArgumentException("null adjacency row");for(int next:row)if(next<0||next>=graph.length)throw new IllegalArgumentException("invalid endpoint");}
}
public static List<Integer> safeNodes(int[][] graph) {
validate(graph);int n=graph.length;List<List<Integer>> reverse=new ArrayList<>();for(int v=0;v<n;v++)reverse.add(new ArrayList<>());
int[] remaining=new int[n];for(int v=0;v<n;v++){remaining[v]=graph[v].length;for(int next:graph[v])reverse.get(next).add(v);}
ArrayDeque<Integer> ready=new ArrayDeque<>();for(int v=0;v<n;v++)if(remaining[v]==0)ready.addLast(v);boolean[] safe=new boolean[n];
while(!ready.isEmpty()) {
int v=ready.removeFirst();safe[v]=true;
for(int predecessor:reverse.get(v))if(--remaining[predecessor]==0)ready.addLast(predecessor);
}
List<Integer> result=new ArrayList<>();for(int v=0;v<n;v++)if(safe[v])result.add(v);return result;
}
public static List<Integer> baseline(int[][] graph) {
validate(graph);int n=graph.length;boolean[][] reach=new boolean[n][n];for(int v=0;v<n;v++)for(int next:graph[v])reach[v][next]=true;
for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)reach[i][j]|=reach[i][k]&&reach[k][j];
List<Integer> result=new ArrayList<>();for(int v=0;v<n;v++){boolean safe=true;for(int c=0;c<n;c++)if(reach[c][c]&&(v==c||reach[v][c])){safe=false;break;}if(safe)result.add(v);}return result;
}
}
Read the meaningful blocks
Reverse adjacency changes propagation direction
For original v→next, store v in reverse[next]. Removing next decrements remaining[v]. Using indegree in the original graph would answer a different question.
Duplicate edges need duplicate reverse entries
A predecessor with two edges to one safe successor starts with remaining two. Both reverse occurrences must be discharged so it reaches zero exactly once.
Do not seed the Floyd baseline identity relation
If reach[v][v] were initialized true for zero-length paths, every isolated vertex would look cyclic. The baseline tracks nonempty paths for cycle detection.
Complexity
For V vertices and E adjacency occurrences, main time is O(V+E+1), and auxiliary reverse lists, remaining counts, queue, and safety flags use O(V+E+1) storage. Returned safe labels use O(S+1) output storage; ascending collection costs O(V), independent of removal order.
The transitive-closure baseline costs O(V³+V²+E+1) time and O(V²+V+1) auxiliary space excluding output. It is not used on the 100,000-vertex boundary. The iterative main method supports long terminal chains and equally long chains feeding a cycle.
Exact-state walkthroughs
Reveal normal and boundary traces
A cycle remains despite an optional terminal branch
Input: [[1,2],[2,3],[5],[0],[5],[],[]] · Ascending universally safe labels: [2,4,5,6]
Step 1 of 11: Seed terminals using original outgoing occurrence counts.
remaining[v] counts outgoing occurrences to successors not yet removed. A terminal is safe without choosing any edge.
Phase: seed.
Original directed edges are outgoing choices. Every choice must terminate.
Vertices — counts include pending edge releases of the current removal
- 02 outgoing remainingoriginal successors: 1, 2
- 12 outgoing remainingoriginal successors: 2, 3
- 21 outgoing remainingoriginal successors: 5
- 31 outgoing remainingoriginal successors: 0
- 41 outgoing remainingoriginal successors: 5
- 50 outgoing remainingoriginal successors: (none)
- 60 outgoing remainingoriginal successors: (none)
Ready FIFO — front at left; newly ready entries append
- 5
- 6
Removed vertices — teaching history
Empty.
Certified safe labels so far — ascending display
Empty.
✓ means every outgoing continuation terminates. One terminal branch is insufficient if another reaches a cycle. Original outdegree counts and reverse edges preserve duplicate occurrences. Final residual vertices can lead into a cycle without belonging to it.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| n | 7 |
| pairs | null |
| graph | [[1,2],[2,3],[5],[0],[5],[],[]] |
| outgoing | [[1,2],[2,3],[5],[0],[5],[],[]] |
| reverse | [[3],[0],[0,1],[1],[],[2,4],[]] |
| remaining | [2,2,1,1,1,0,0] |
| ready | [5,6] |
| removed | [] |
| order | [] |
| safe | [false,false,false,false,false,false,false] |
| completed | 0 |
| semesters | 0 |
| leftInLayer | 0 |
| current | null |
| phase | "seed" |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(int[][] graph) { 4 Objects.requireNonNull(graph,"graph");for(int[] row:graph){if(row==null)throw new IllegalArgumentException("null adjacency row");for(int next:row)if(next<0||next>=graph.length)throw new IllegalArgumentException("invalid endpoint");} 5 } 6 public static List<Integer> safeNodes(int[][] graph) { 7 validate(graph);int n=graph.length;List<List<Integer>> reverse=new ArrayList<>();for(int v=0;v<n;v++)reverse.add(new ArrayList<>()); 8 int[] remaining=new int[n];for(int v=0;v<n;v++){remaining[v]=graph[v].length;for(int next:graph[v])reverse.get(next).add(v);} 9 ArrayDeque<Integer> ready=new ArrayDeque<>();for(int v=0;v<n;v++)if(remaining[v]==0)ready.addLast(v);boolean[] safe=new boolean[n]; 10 while(!ready.isEmpty()) { 11 int v=ready.removeFirst();safe[v]=true; 12 for(int predecessor:reverse.get(v))if(--remaining[predecessor]==0)ready.addLast(predecessor); 13 } 14 List<Integer> result=new ArrayList<>();for(int v=0;v<n;v++)if(safe[v])result.add(v);return result; 15 } 16 public static List<Integer> baseline(int[][] graph) { 17 validate(graph);int n=graph.length;boolean[][] reach=new boolean[n][n];for(int v=0;v<n;v++)for(int next:graph[v])reach[v][next]=true; 18 for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)reach[i][j]|=reach[i][k]&&reach[k][j]; 19 List<Integer> result=new ArrayList<>();for(int v=0;v<n;v++){boolean safe=true;for(int c=0;c<n;c++)if(reach[c][c]&&(v==c||reach[v][c])){safe=false;break;}if(safe)result.add(v);}return result; 20 } 21 } 22
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed terminals using original outgoing occurrence counts.
remaining[v] counts outgoing occurrences to successors not yet removed. A terminal is safe without choosing any edge.
- n
7- pairs
null- graph
[[1,2],[2,3],[5],[0],[5],[],[]]- outgoing
[[1,2],[2,3],[5],[0],[5],[],[]]- reverse
[[3],[0],[0,1],[1],[],[2,4],[]]- remaining
[2,2,1,1,1,0,0]- ready
[5,6]- removed
[]- order
[]- safe
[false,false,false,false,false,false,false]- completed
0- semesters
0- leftInLayer
0- current
null- phase
"seed"
- Certify a vertex whose every successor is already safe.
Safety means every possible path terminates, not merely that one terminal is reachable.
- n
7- pairs
null- graph
[[1,2],[2,3],[5],[0],[5],[],[]]- outgoing
[[1,2],[2,3],[5],[0],[5],[],[]]- reverse
[[3],[0],[0,1],[1],[],[2,4],[]]- remaining
[2,2,1,1,1,0,0]- ready
[6]- removed
[5]- order
[]- safe
[false,false,false,false,false,true,false]- completed
1- semesters
0- leftInLayer
0- current
5- phase
"remove"
- Remove one edge occurrence and test the transition to zero.
Repeated edges are counted and removed with matching multiplicity. Zero is reached once; queue contents use FIFO order, not global sorting.
- n
7- pairs
null- graph
[[1,2],[2,3],[5],[0],[5],[],[]]- outgoing
[[1,2],[2,3],[5],[0],[5],[],[]]- reverse
[[3],[0],[0,1],[1],[],[2,4],[]]- remaining
[2,2,0,1,1,0,0]- ready
[6,2]- removed
[5]- order
[]- safe
[false,false,false,false,false,true,false]- completed
1- semesters
0- leftInLayer
0- current
5- phase
"release"- next
2- edgeIndex
0
- Remove one edge occurrence and test the transition to zero.
Repeated edges are counted and removed with matching multiplicity. Zero is reached once; queue contents use FIFO order, not global sorting.
- n
7- pairs
null- graph
[[1,2],[2,3],[5],[0],[5],[],[]]- outgoing
[[1,2],[2,3],[5],[0],[5],[],[]]- reverse
[[3],[0],[0,1],[1],[],[2,4],[]]- remaining
[2,2,0,1,0,0,0]- ready
[6,2,4]- removed
[5]- order
[]- safe
[false,false,false,false,false,true,false]- completed
1- semesters
0- leftInLayer
0- current
5- phase
"release"- next
4- edgeIndex
1
- Certify a vertex whose every successor is already safe.
Safety means every possible path terminates, not merely that one terminal is reachable.
- n
7- pairs
null- graph
[[1,2],[2,3],[5],[0],[5],[],[]]- outgoing
[[1,2],[2,3],[5],[0],[5],[],[]]- reverse
[[3],[0],[0,1],[1],[],[2,4],[]]- remaining
[2,2,0,1,0,0,0]- ready
[2,4]- removed
[5,6]- order
[]- safe
[false,false,false,false,false,true,true]- completed
2- semesters
0- leftInLayer
0- current
6- phase
"remove"
- Certify a vertex whose every successor is already safe.
Safety means every possible path terminates, not merely that one terminal is reachable.
- n
7- pairs
null- graph
[[1,2],[2,3],[5],[0],[5],[],[]]- outgoing
[[1,2],[2,3],[5],[0],[5],[],[]]- reverse
[[3],[0],[0,1],[1],[],[2,4],[]]- remaining
[2,2,0,1,0,0,0]- ready
[4]- removed
[5,6,2]- order
[]- safe
[false,false,true,false,false,true,true]- completed
3- semesters
0- leftInLayer
0- current
2- phase
"remove"
- Remove one edge occurrence and test the transition to zero.
Repeated edges are counted and removed with matching multiplicity. Zero is reached once; queue contents use FIFO order, not global sorting.
- n
7- pairs
null- graph
[[1,2],[2,3],[5],[0],[5],[],[]]- outgoing
[[1,2],[2,3],[5],[0],[5],[],[]]- reverse
[[3],[0],[0,1],[1],[],[2,4],[]]- remaining
[1,2,0,1,0,0,0]- ready
[4]- removed
[5,6,2]- order
[]- safe
[false,false,true,false,false,true,true]- completed
3- semesters
0- leftInLayer
0- current
2- phase
"release"- next
0- edgeIndex
0
- Remove one edge occurrence and test the transition to zero.
Repeated edges are counted and removed with matching multiplicity. Zero is reached once; queue contents use FIFO order, not global sorting.
- n
7- pairs
null- graph
[[1,2],[2,3],[5],[0],[5],[],[]]- outgoing
[[1,2],[2,3],[5],[0],[5],[],[]]- reverse
[[3],[0],[0,1],[1],[],[2,4],[]]- remaining
[1,1,0,1,0,0,0]- ready
[4]- removed
[5,6,2]- order
[]- safe
[false,false,true,false,false,true,true]- completed
3- semesters
0- leftInLayer
0- current
2- phase
"release"- next
1- edgeIndex
1
- Certify a vertex whose every successor is already safe.
Safety means every possible path terminates, not merely that one terminal is reachable.
- n
7- pairs
null- graph
[[1,2],[2,3],[5],[0],[5],[],[]]- outgoing
[[1,2],[2,3],[5],[0],[5],[],[]]- reverse
[[3],[0],[0,1],[1],[],[2,4],[]]- remaining
[1,1,0,1,0,0,0]- ready
[]- removed
[5,6,2,4]- order
[]- safe
[false,false,true,false,true,true,true]- completed
4- semesters
0- leftInLayer
0- current
4- phase
"remove"
- Collect safe vertices in ascending numeric order.
Residual vertices reach or belong to a directed cycle. Removal order can differ from the ascending returned list.
- n
7- pairs
null- graph
[[1,2],[2,3],[5],[0],[5],[],[]]- outgoing
[[1,2],[2,3],[5],[0],[5],[],[]]- reverse
[[3],[0],[0,1],[1],[],[2,4],[]]- remaining
[1,1,0,1,0,0,0]- ready
[]- removed
[5,6,2,4]- order
[]- safe
[false,false,true,false,true,true,true]- completed
4- semesters
0- leftInLayer
0- current
null- phase
"complete"
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
[2,4,5,6]
Parallel successor occurrences discharge together
Input: [[1,1],[],[2]] · Ascending universally safe labels: [0,1]
Step 1 of 7: Seed terminals using original outgoing occurrence counts.
remaining[v] counts outgoing occurrences to successors not yet removed. A terminal is safe without choosing any edge.
Phase: seed.
Original directed edges are outgoing choices. Every choice must terminate.
Vertices — counts include pending edge releases of the current removal
- 02 outgoing remainingoriginal successors: 1, 1
- 10 outgoing remainingoriginal successors: (none)
- 21 outgoing remainingoriginal successors: 2
Ready FIFO — front at left; newly ready entries append
- 1
Removed vertices — teaching history
Empty.
Certified safe labels so far — ascending display
Empty.
✓ means every outgoing continuation terminates. One terminal branch is insufficient if another reaches a cycle. Original outdegree counts and reverse edges preserve duplicate occurrences. Final residual vertices can lead into a cycle without belonging to it.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| n | 3 |
| pairs | null |
| graph | [[1,1],[],[2]] |
| outgoing | [[1,1],[],[2]] |
| reverse | [[],[0,0],[2]] |
| remaining | [2,0,1] |
| ready | [1] |
| removed | [] |
| order | [] |
| safe | [false,false,false] |
| completed | 0 |
| semesters | 0 |
| leftInLayer | 0 |
| current | null |
| phase | "seed" |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(int[][] graph) { 4 Objects.requireNonNull(graph,"graph");for(int[] row:graph){if(row==null)throw new IllegalArgumentException("null adjacency row");for(int next:row)if(next<0||next>=graph.length)throw new IllegalArgumentException("invalid endpoint");} 5 } 6 public static List<Integer> safeNodes(int[][] graph) { 7 validate(graph);int n=graph.length;List<List<Integer>> reverse=new ArrayList<>();for(int v=0;v<n;v++)reverse.add(new ArrayList<>()); 8 int[] remaining=new int[n];for(int v=0;v<n;v++){remaining[v]=graph[v].length;for(int next:graph[v])reverse.get(next).add(v);} 9 ArrayDeque<Integer> ready=new ArrayDeque<>();for(int v=0;v<n;v++)if(remaining[v]==0)ready.addLast(v);boolean[] safe=new boolean[n]; 10 while(!ready.isEmpty()) { 11 int v=ready.removeFirst();safe[v]=true; 12 for(int predecessor:reverse.get(v))if(--remaining[predecessor]==0)ready.addLast(predecessor); 13 } 14 List<Integer> result=new ArrayList<>();for(int v=0;v<n;v++)if(safe[v])result.add(v);return result; 15 } 16 public static List<Integer> baseline(int[][] graph) { 17 validate(graph);int n=graph.length;boolean[][] reach=new boolean[n][n];for(int v=0;v<n;v++)for(int next:graph[v])reach[v][next]=true; 18 for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)reach[i][j]|=reach[i][k]&&reach[k][j]; 19 List<Integer> result=new ArrayList<>();for(int v=0;v<n;v++){boolean safe=true;for(int c=0;c<n;c++)if(reach[c][c]&&(v==c||reach[v][c])){safe=false;break;}if(safe)result.add(v);}return result; 20 } 21 } 22
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed terminals using original outgoing occurrence counts.
remaining[v] counts outgoing occurrences to successors not yet removed. A terminal is safe without choosing any edge.
- n
3- pairs
null- graph
[[1,1],[],[2]]- outgoing
[[1,1],[],[2]]- reverse
[[],[0,0],[2]]- remaining
[2,0,1]- ready
[1]- removed
[]- order
[]- safe
[false,false,false]- completed
0- semesters
0- leftInLayer
0- current
null- phase
"seed"
- Certify a vertex whose every successor is already safe.
Safety means every possible path terminates, not merely that one terminal is reachable.
- n
3- pairs
null- graph
[[1,1],[],[2]]- outgoing
[[1,1],[],[2]]- reverse
[[],[0,0],[2]]- remaining
[2,0,1]- ready
[]- removed
[1]- order
[]- safe
[false,true,false]- completed
1- semesters
0- leftInLayer
0- current
1- phase
"remove"
- Remove one edge occurrence and test the transition to zero.
Repeated edges are counted and removed with matching multiplicity. Zero is reached once; queue contents use FIFO order, not global sorting.
- n
3- pairs
null- graph
[[1,1],[],[2]]- outgoing
[[1,1],[],[2]]- reverse
[[],[0,0],[2]]- remaining
[1,0,1]- ready
[]- removed
[1]- order
[]- safe
[false,true,false]- completed
1- semesters
0- leftInLayer
0- current
1- phase
"release"- next
0- edgeIndex
0
- Remove one edge occurrence and test the transition to zero.
Repeated edges are counted and removed with matching multiplicity. Zero is reached once; queue contents use FIFO order, not global sorting.
- n
3- pairs
null- graph
[[1,1],[],[2]]- outgoing
[[1,1],[],[2]]- reverse
[[],[0,0],[2]]- remaining
[0,0,1]- ready
[0]- removed
[1]- order
[]- safe
[false,true,false]- completed
1- semesters
0- leftInLayer
0- current
1- phase
"release"- next
0- edgeIndex
1
- Certify a vertex whose every successor is already safe.
Safety means every possible path terminates, not merely that one terminal is reachable.
- n
3- pairs
null- graph
[[1,1],[],[2]]- outgoing
[[1,1],[],[2]]- reverse
[[],[0,0],[2]]- remaining
[0,0,1]- ready
[]- removed
[1,0]- order
[]- safe
[true,true,false]- completed
2- semesters
0- leftInLayer
0- current
0- phase
"remove"
- Collect safe vertices in ascending numeric order.
Residual vertices reach or belong to a directed cycle. Removal order can differ from the ascending returned list.
- n
3- pairs
null- graph
[[1,1],[],[2]]- outgoing
[[1,1],[],[2]]- reverse
[[],[0,0],[2]]- remaining
[0,0,1]- ready
[]- removed
[1,0]- order
[]- safe
[true,true,false]- completed
2- semesters
0- leftInLayer
0- current
null- phase
"complete"
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
[0,1]
All vertices are terminals
Input: [[],[],[]] · Ascending universally safe labels: [0,1,2]
Step 1 of 6: Seed terminals using original outgoing occurrence counts.
remaining[v] counts outgoing occurrences to successors not yet removed. A terminal is safe without choosing any edge.
Phase: seed.
Original directed edges are outgoing choices. Every choice must terminate.
Vertices — counts include pending edge releases of the current removal
- 00 outgoing remainingoriginal successors: (none)
- 10 outgoing remainingoriginal successors: (none)
- 20 outgoing remainingoriginal successors: (none)
Ready FIFO — front at left; newly ready entries append
- 0
- 1
- 2
Removed vertices — teaching history
Empty.
Certified safe labels so far — ascending display
Empty.
✓ means every outgoing continuation terminates. One terminal branch is insufficient if another reaches a cycle. Original outdegree counts and reverse edges preserve duplicate occurrences. Final residual vertices can lead into a cycle without belonging to it.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| n | 3 |
| pairs | null |
| graph | [[],[],[]] |
| outgoing | [[],[],[]] |
| reverse | [[],[],[]] |
| remaining | [0,0,0] |
| ready | [0,1,2] |
| removed | [] |
| order | [] |
| safe | [false,false,false] |
| completed | 0 |
| semesters | 0 |
| leftInLayer | 0 |
| current | null |
| phase | "seed" |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(int[][] graph) { 4 Objects.requireNonNull(graph,"graph");for(int[] row:graph){if(row==null)throw new IllegalArgumentException("null adjacency row");for(int next:row)if(next<0||next>=graph.length)throw new IllegalArgumentException("invalid endpoint");} 5 } 6 public static List<Integer> safeNodes(int[][] graph) { 7 validate(graph);int n=graph.length;List<List<Integer>> reverse=new ArrayList<>();for(int v=0;v<n;v++)reverse.add(new ArrayList<>()); 8 int[] remaining=new int[n];for(int v=0;v<n;v++){remaining[v]=graph[v].length;for(int next:graph[v])reverse.get(next).add(v);} 9 ArrayDeque<Integer> ready=new ArrayDeque<>();for(int v=0;v<n;v++)if(remaining[v]==0)ready.addLast(v);boolean[] safe=new boolean[n]; 10 while(!ready.isEmpty()) { 11 int v=ready.removeFirst();safe[v]=true; 12 for(int predecessor:reverse.get(v))if(--remaining[predecessor]==0)ready.addLast(predecessor); 13 } 14 List<Integer> result=new ArrayList<>();for(int v=0;v<n;v++)if(safe[v])result.add(v);return result; 15 } 16 public static List<Integer> baseline(int[][] graph) { 17 validate(graph);int n=graph.length;boolean[][] reach=new boolean[n][n];for(int v=0;v<n;v++)for(int next:graph[v])reach[v][next]=true; 18 for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)reach[i][j]|=reach[i][k]&&reach[k][j]; 19 List<Integer> result=new ArrayList<>();for(int v=0;v<n;v++){boolean safe=true;for(int c=0;c<n;c++)if(reach[c][c]&&(v==c||reach[v][c])){safe=false;break;}if(safe)result.add(v);}return result; 20 } 21 } 22
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed terminals using original outgoing occurrence counts.
remaining[v] counts outgoing occurrences to successors not yet removed. A terminal is safe without choosing any edge.
- n
3- pairs
null- graph
[[],[],[]]- outgoing
[[],[],[]]- reverse
[[],[],[]]- remaining
[0,0,0]- ready
[0,1,2]- removed
[]- order
[]- safe
[false,false,false]- completed
0- semesters
0- leftInLayer
0- current
null- phase
"seed"
- Certify a vertex whose every successor is already safe.
Safety means every possible path terminates, not merely that one terminal is reachable.
- n
3- pairs
null- graph
[[],[],[]]- outgoing
[[],[],[]]- reverse
[[],[],[]]- remaining
[0,0,0]- ready
[1,2]- removed
[0]- order
[]- safe
[true,false,false]- completed
1- semesters
0- leftInLayer
0- current
0- phase
"remove"
- Certify a vertex whose every successor is already safe.
Safety means every possible path terminates, not merely that one terminal is reachable.
- n
3- pairs
null- graph
[[],[],[]]- outgoing
[[],[],[]]- reverse
[[],[],[]]- remaining
[0,0,0]- ready
[2]- removed
[0,1]- order
[]- safe
[true,true,false]- completed
2- semesters
0- leftInLayer
0- current
1- phase
"remove"
- Certify a vertex whose every successor is already safe.
Safety means every possible path terminates, not merely that one terminal is reachable.
- n
3- pairs
null- graph
[[],[],[]]- outgoing
[[],[],[]]- reverse
[[],[],[]]- remaining
[0,0,0]- ready
[]- removed
[0,1,2]- order
[]- safe
[true,true,true]- completed
3- semesters
0- leftInLayer
0- current
2- phase
"remove"
- Collect safe vertices in ascending numeric order.
Residual vertices reach or belong to a directed cycle. Removal order can differ from the ascending returned list.
- n
3- pairs
null- graph
[[],[],[]]- outgoing
[[],[],[]]- reverse
[[],[],[]]- remaining
[0,0,0]- ready
[]- removed
[0,1,2]- order
[]- safe
[true,true,true]- completed
3- semesters
0- leftInLayer
0- current
null- phase
"complete"
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
[0,1,2]
One terminal branch does not certify universal safety
Input: [[1,2],[],[2]] · Ascending universally safe labels: [1]
Step 1 of 5: Seed terminals using original outgoing occurrence counts.
remaining[v] counts outgoing occurrences to successors not yet removed. A terminal is safe without choosing any edge.
Phase: seed.
Original directed edges are outgoing choices. Every choice must terminate.
Vertices — counts include pending edge releases of the current removal
- 02 outgoing remainingoriginal successors: 1, 2
- 10 outgoing remainingoriginal successors: (none)
- 21 outgoing remainingoriginal successors: 2
Ready FIFO — front at left; newly ready entries append
- 1
Removed vertices — teaching history
Empty.
Certified safe labels so far — ascending display
Empty.
✓ means every outgoing continuation terminates. One terminal branch is insufficient if another reaches a cycle. Original outdegree counts and reverse edges preserve duplicate occurrences. Final residual vertices can lead into a cycle without belonging to it.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| n | 3 |
| pairs | null |
| graph | [[1,2],[],[2]] |
| outgoing | [[1,2],[],[2]] |
| reverse | [[],[0],[0,2]] |
| remaining | [2,0,1] |
| ready | [1] |
| removed | [] |
| order | [] |
| safe | [false,false,false] |
| completed | 0 |
| semesters | 0 |
| leftInLayer | 0 |
| current | null |
| phase | "seed" |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(int[][] graph) { 4 Objects.requireNonNull(graph,"graph");for(int[] row:graph){if(row==null)throw new IllegalArgumentException("null adjacency row");for(int next:row)if(next<0||next>=graph.length)throw new IllegalArgumentException("invalid endpoint");} 5 } 6 public static List<Integer> safeNodes(int[][] graph) { 7 validate(graph);int n=graph.length;List<List<Integer>> reverse=new ArrayList<>();for(int v=0;v<n;v++)reverse.add(new ArrayList<>()); 8 int[] remaining=new int[n];for(int v=0;v<n;v++){remaining[v]=graph[v].length;for(int next:graph[v])reverse.get(next).add(v);} 9 ArrayDeque<Integer> ready=new ArrayDeque<>();for(int v=0;v<n;v++)if(remaining[v]==0)ready.addLast(v);boolean[] safe=new boolean[n]; 10 while(!ready.isEmpty()) { 11 int v=ready.removeFirst();safe[v]=true; 12 for(int predecessor:reverse.get(v))if(--remaining[predecessor]==0)ready.addLast(predecessor); 13 } 14 List<Integer> result=new ArrayList<>();for(int v=0;v<n;v++)if(safe[v])result.add(v);return result; 15 } 16 public static List<Integer> baseline(int[][] graph) { 17 validate(graph);int n=graph.length;boolean[][] reach=new boolean[n][n];for(int v=0;v<n;v++)for(int next:graph[v])reach[v][next]=true; 18 for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)reach[i][j]|=reach[i][k]&&reach[k][j]; 19 List<Integer> result=new ArrayList<>();for(int v=0;v<n;v++){boolean safe=true;for(int c=0;c<n;c++)if(reach[c][c]&&(v==c||reach[v][c])){safe=false;break;}if(safe)result.add(v);}return result; 20 } 21 } 22
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed terminals using original outgoing occurrence counts.
remaining[v] counts outgoing occurrences to successors not yet removed. A terminal is safe without choosing any edge.
- n
3- pairs
null- graph
[[1,2],[],[2]]- outgoing
[[1,2],[],[2]]- reverse
[[],[0],[0,2]]- remaining
[2,0,1]- ready
[1]- removed
[]- order
[]- safe
[false,false,false]- completed
0- semesters
0- leftInLayer
0- current
null- phase
"seed"
- Certify a vertex whose every successor is already safe.
Safety means every possible path terminates, not merely that one terminal is reachable.
- n
3- pairs
null- graph
[[1,2],[],[2]]- outgoing
[[1,2],[],[2]]- reverse
[[],[0],[0,2]]- remaining
[2,0,1]- ready
[]- removed
[1]- order
[]- safe
[false,true,false]- completed
1- semesters
0- leftInLayer
0- current
1- phase
"remove"
- Remove one edge occurrence and test the transition to zero.
Repeated edges are counted and removed with matching multiplicity. Zero is reached once; queue contents use FIFO order, not global sorting.
- n
3- pairs
null- graph
[[1,2],[],[2]]- outgoing
[[1,2],[],[2]]- reverse
[[],[0],[0,2]]- remaining
[1,0,1]- ready
[]- removed
[1]- order
[]- safe
[false,true,false]- completed
1- semesters
0- leftInLayer
0- current
1- phase
"release"- next
0- edgeIndex
0
- Collect safe vertices in ascending numeric order.
Residual vertices reach or belong to a directed cycle. Removal order can differ from the ascending returned list.
- n
3- pairs
null- graph
[[1,2],[],[2]]- outgoing
[[1,2],[],[2]]- reverse
[[],[0],[0,2]]- remaining
[1,0,1]- ready
[]- removed
[1]- order
[]- safe
[false,true,false]- completed
1- semesters
0- leftInLayer
0- current
null- phase
"complete"
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
[1]
Empty graph
Input: [] · Ascending universally safe labels: []
Step 1 of 3: Seed terminals using original outgoing occurrence counts.
remaining[v] counts outgoing occurrences to successors not yet removed. A terminal is safe without choosing any edge.
Phase: seed.
Original directed edges are outgoing choices. Every choice must terminate.
Vertices — counts include pending edge releases of the current removal
Ready FIFO — front at left; newly ready entries append
Empty.
Removed vertices — teaching history
Empty.
Certified safe labels so far — ascending display
Empty.
✓ means every outgoing continuation terminates. One terminal branch is insufficient if another reaches a cycle. Original outdegree counts and reverse edges preserve duplicate occurrences. Final residual vertices can lead into a cycle without belonging to it.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| n | 0 |
| pairs | null |
| graph | [] |
| outgoing | [] |
| reverse | [] |
| remaining | [] |
| ready | [] |
| removed | [] |
| order | [] |
| safe | [] |
| completed | 0 |
| semesters | 0 |
| leftInLayer | 0 |
| current | null |
| phase | "seed" |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(int[][] graph) { 4 Objects.requireNonNull(graph,"graph");for(int[] row:graph){if(row==null)throw new IllegalArgumentException("null adjacency row");for(int next:row)if(next<0||next>=graph.length)throw new IllegalArgumentException("invalid endpoint");} 5 } 6 public static List<Integer> safeNodes(int[][] graph) { 7 validate(graph);int n=graph.length;List<List<Integer>> reverse=new ArrayList<>();for(int v=0;v<n;v++)reverse.add(new ArrayList<>()); 8 int[] remaining=new int[n];for(int v=0;v<n;v++){remaining[v]=graph[v].length;for(int next:graph[v])reverse.get(next).add(v);} 9 ArrayDeque<Integer> ready=new ArrayDeque<>();for(int v=0;v<n;v++)if(remaining[v]==0)ready.addLast(v);boolean[] safe=new boolean[n]; 10 while(!ready.isEmpty()) { 11 int v=ready.removeFirst();safe[v]=true; 12 for(int predecessor:reverse.get(v))if(--remaining[predecessor]==0)ready.addLast(predecessor); 13 } 14 List<Integer> result=new ArrayList<>();for(int v=0;v<n;v++)if(safe[v])result.add(v);return result; 15 } 16 public static List<Integer> baseline(int[][] graph) { 17 validate(graph);int n=graph.length;boolean[][] reach=new boolean[n][n];for(int v=0;v<n;v++)for(int next:graph[v])reach[v][next]=true; 18 for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)reach[i][j]|=reach[i][k]&&reach[k][j]; 19 List<Integer> result=new ArrayList<>();for(int v=0;v<n;v++){boolean safe=true;for(int c=0;c<n;c++)if(reach[c][c]&&(v==c||reach[v][c])){safe=false;break;}if(safe)result.add(v);}return result; 20 } 21 } 22
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed terminals using original outgoing occurrence counts.
remaining[v] counts outgoing occurrences to successors not yet removed. A terminal is safe without choosing any edge.
- n
0- pairs
null- graph
[]- outgoing
[]- reverse
[]- remaining
[]- ready
[]- removed
[]- order
[]- safe
[]- completed
0- semesters
0- leftInLayer
0- current
null- phase
"seed"
- Collect safe vertices in ascending numeric order.
Residual vertices reach or belong to a directed cycle. Removal order can differ from the ascending returned list.
- n
0- pairs
null- graph
[]- outgoing
[]- reverse
[]- remaining
[]- ready
[]- removed
[]- order
[]- safe
[]- completed
0- semesters
0- leftInLayer
0- current
null- phase
"complete"
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
[]
Test the contract
Input:
All terminal vertices
Output:all labels ascendingEvery zero-outdegree base case is safe.
Input:
Self-loop plus predecessors
Output:cycle and every predecessor excludedExistence of a nonterminating choice is enough.
Input:
Repeated outgoing occurrences and aliased rows
Output:correct safe set with preserved inputCounts and reverse entries match.
Input:
100,000-node terminal chain / chain feeding a loop
Output:all labels / empty listMain implementation is deep-safe.
Input:
Edit one returned list, then call again
Output:independent mutable outputThe result does not alias another call or source row.
Common mistakes and counterexamples
Accept any vertex that can reach a terminal
Counterexample: 0→terminal and 0→self-loop contains one good path and one infinite path.
Wait until all outgoing occurrences are certified.
Peel original indegree zeroes
Counterexample: A source can point directly into a cycle and be unsafe.
Count original outdegree and propagate through reverse adjacency.
Return queue removal order as ascending output
Counterexample: In [[1,1],[],[2]], 1 is removed before 0.
Collect certified labels with a separate ascending scan.
Call every residual vertex a cycle member
Counterexample: A chain leading into a self-loop is entirely unsafe, but only its last vertex is on the cycle.
Describe the residual as cycle-reachable.
Follow-ups
Produce an unsafe-path witness.
Use the residual graph to follow residual outgoing edges until repetition; split the resulting walk into a prefix and cycle. Keep object/label indices so the repeated section is verifiable.
Use active/finished DFS instead.
Track recursion-stack membership separately from completed safe/unsafe memo states. Use explicit continuation frames for long chains and propagate unsafe results to ancestors.
Explain the difference from terminal reachability.
Compare the existential set obtained by ordinary reverse BFS with the universal safe set. A vertex with one terminal branch and one cyclic branch belongs only to the former.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 161/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.