Hints — p62 Course Schedule II

Hint 1. This is topological sort. Edge convention: [a, b] means “b before a” → directed edge b → a. Get the direction right or you’ll output the reverse order.

Hint 2. Kahn’s BFS: build adjacency + indegree array. Push all indegree-0 nodes onto a queue. Pop, append to result, decrement neighbors’ indegrees; if any drops to 0, push. Cycle iff final result has fewer than n nodes.

Hint 3. DFS alternative: three colors WHITE/GRAY/BLACK. On entering, mark GRAY; recurse on neighbors; if any is GRAY → back-edge → cycle. On finish, mark BLACK and append to a post-order list. Reverse it at the end.

Hint 4. Both are O(V + E). Watch for: self-loops [a, a] (cycle of length 1), disconnected components (loop over all start nodes).

Hint 5. Use iterative DFS (explicit stack) for n > 1000 to avoid Python recursion limit, or call sys.setrecursionlimit. Follow-up “lex-smallest order” → swap Kahn’s deque for a heapq.

If stuck: see solution.py.