Course Schedule

LeetCode 207 • Medium • Graph

There are numCourses courses labeled 0 .. numCourses-1. prerequisites[i] = [a, b] means you must take course b before a. Return whether you can finish all courses (DAG = no directed cycle).

TimeO(V+E)each edge once

SpaceO(V+E)graph + queue

Step0/0

Unprocessed In queue Finished

Ready

Kahn: repeatedly pick a course with indegree 0. If you process all n courses, no cycle.

Speed:

✎ Whiteboard

Size:3

⌨ Type It

Implement canFinish(numCourses, prerequisites).

═══ KAHN (TOPO SORT) ═══

indegree[v]++; adj[b].append(a) for [a,b]

queue all v with indegree 0

while queue: pop v; count++; relax edges

return count == numCourses

Verify:

⌨ Type It — DFS

Verify: