LeetCode 207 · Medium · Graphs

Course Schedule

There are numCourses courses, and a pair [a, b] means you must take b before a. Return true if you can finish every course, which is the same as the prerequisite graph having no cycle.

O(V + E)time
O(V + E)space
DFSa visiting course seen again = cycle

numCourses 1–8 · up to 12 distinct pairs [course, prerequisite], courses 0 to numCourses − 1

visiting the dfs path, bottom → top

private List<List<Integer>> preMap = new ArrayList<>();private Set<Integer> visiting = new HashSet<>(); // on the current dfs pathpublic boolean canFinish(int numCourses, int[][] prerequisites) { for (int i = 0; i < numCourses; i++) { preMap.add(new ArrayList<>()); } for (int[] p : prerequisites) { preMap.get(p[0]).add(p[1]); } for (int c = 0; c < numCourses; c++) { if (!dfs(c)) { return false; } } return true;}private boolean dfs(int crs) { if (visiting.contains(crs)) { return false; // back on the path: a cycle } if (preMap.get(crs).isEmpty()) { return true; } visiting.add(crs); for (int pre : preMap.get(crs)) { if (!dfs(pre)) { return false; } } visiting.remove(crs); preMap.get(crs).clear(); // finished: no cycle through crs return true;}
c
—
crs
—
preMap.get(crs)
—
visiting
{}
finished
0

Why it works

  1. Brute force tries every order of the courses and checks each against the pairs: O(V!·E). The real question is only whether the graph has a cycle.
  2. Three states make the cycle visible. A course is unvisited, visiting (on the current DFS path) or finished. Reaching a visiting course means following prerequisites led back to a course still waiting on them: a cycle. Reaching a finished course is safe.
  3. O(V + E): calling preMap.get(crs).clear() when a course finishes turns every later call into an O(1) return, so each course is expanded once and each pair is followed once.
  4. Pitfall: one set is not enough. If finished courses stayed in visiting, the diamond preset would report a false cycle when course 3 reaches course 1, which already finished. Remove the course from visiting on the way out.
  5. Follow-up: Course Schedule II (210) returns an order too: append each course as it finishes. Kahn's algorithm (BFS on in-degrees) answers both without recursion.