Exercise 2: Course Schedule — Can You Finish? 🎓

Your Task

There are numCourses courses labeled 0 to numCourses - 1. You're given a list of prerequisites where prerequisites[i] = [a, b] means you must take course b before course a.

Return True if you can finish all courses, or False if there's a cycle in the prerequisites (making it impossible).

This is LeetCode 207: Course Schedule.

---

Examples

print(can_finish(2, [[1, 0]]))
# Output: True
# Take course 0, then course 1

print(can_finish(2, [[1, 0], [0, 1]]))
# Output: False
# Course 0 requires 1, and course 1 requires 0 — cycle!

print(can_finish(4, [[1, 0], [2, 1], [3, 2]]))
# Output: True
# Linear chain: 0 → 1 → 2 → 3

print(can_finish(4, [[1, 0], [2, 1], [3, 2], [0, 3]]))
# Output: False
# Cycle: 0 → 1 → 2 → 3 → 0

---

Expected Complexity

	Complexity
Time	O(V + E)
Space	O(V + E)

Where V = numCourses and E = number of prerequisites.

Why? We build an adjacency list (O(V + E)), then DFS visits each node and edge at most once.

---

Approach — DFS with 3 Colors

Use the WHITE / GRAY / BLACK technique:

1. Build an adjacency list from the prerequisites
2. Initialize every node as WHITE (unvisited)
3. DFS from each WHITE node:
   • Mark it GRAY (in progress — on the current path)
   • Visit all neighbors recursively
   • If you hit a GRAY node → cycle found! Return False
   • If BLACK → already done, skip
   • Mark it BLACK when all neighbors are explored
4. If no cycles found across all nodes, return True

---

Starter Code

def can_finish(numCourses, prerequisites):
    # Your code here
    pass

# Test your function:
print(can_finish(2, [[1, 0]]))
# Output: True

print(can_finish(2, [[1, 0], [0, 1]]))
# Output: False

print(can_finish(4, [[1, 0], [2, 1], [3, 2]]))
# Output: True

print(can_finish(4, [[1, 0], [2, 1], [3, 2], [0, 3]]))
# Output: False

print(can_finish(5, [[1,0], [2,0], [3,1], [3,2], [4,3]]))
# Output: True

---

Hints

---

Bonus Challenge 🌟

What if the prerequisites could also have a self-loop like [1, 1] (course 1 requires itself)? Does your solution handle it? Test it!

print(can_finish(3, [[1, 0], [1, 1], [2, 1]]))
# Output: False (course 1 requires itself — impossible!)