Course Schedule II Visualizer

cycle set the dfs path, bottom → top

output courses in the order they finish

private List<List<Integer>> prereq = new ArrayList<>();private List<Integer> output = new ArrayList<>();private Set<Integer> visit = new HashSet<>();private Set<Integer> cycle = new HashSet<>();public int[] findOrder(int numCourses, int[][] prerequisites) { for (int i = 0; i < numCourses; i++) { prereq.add(new ArrayList<>()); } for (int[] p : prerequisites) { prereq.get(p[0]).add(p[1]); } for (int c = 0; c < numCourses; c++) { if (!dfs(c)) { return new int[0]; } } int[] res = new int[numCourses]; for (int i = 0; i < numCourses; i++) { res[i] = output.get(i); } return res;}private boolean dfs(int crs) { if (cycle.contains(crs)) { return false; // back on the path } if (visit.contains(crs)) { return true; // already in output } cycle.add(crs); for (int pre : prereq.get(crs)) { if (!dfs(pre)) { return false; } } cycle.remove(crs); visit.add(crs); output.add(crs); // all its prerequisites are in return true;}

c: —
crs: —
cycle: {}
visit: {}
output: []

Why it works

Brute force tries orders of the courses until one respects every pair: O(V!·E).
Post-order is a topological order. A course is appended only after dfs returned for each of its prerequisites, and each of those was appended before it (or earlier still). So every prerequisite sits to the left of the courses that need it.
Two sets, three states. cycle holds the courses on the current path (visiting), visit the finished ones. Meeting a course in cycle is a cycle; meeting one in visit is an O(1) return, so each course and each pair is handled once: O(V + E).
Pitfall: append on the way out, not on the way in. Appending when a course enters cycle puts it before its own prerequisites.
Alternative: Kahn's algorithm takes courses with no remaining prerequisites from a queue; if fewer than numCourses come out, there is a cycle. Alien Dictionary (269) builds the graph from word pairs and then runs this same sort.