Course Schedule Cycle Detection

Given courses and prerequisite pairs, determine whether all courses can be completed by detecting cycles in a directed graph. Requirements Implement the classic Course Schedule decision problem: def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool: ... Expected behavior: Treat each course as a directed-graph node. Treat each prerequisite pair as an edge. Return False if the graph contains a directed cycle. Return True if all nodes can be processed in a valid topological order. Explain both DFS cycle detection and BFS topological sort if asked. Notes The DFS version needs three states, not just a single visited set: 0 = unvisited 1 = visiting, currently in this DFS path 2 = done, already proven acyclic If DFS reaches a visiting node, it has found a cycle. If it reaches a done node, it can stop early. The BFS version uses indegrees and a queue of zero-indegree nodes; if fewer than num_courses nodes are popped, a cycle remains. Complexity is O(V + E) time and O(V + E) space. Preparation Write both DFS and Kahn's algorithm from memory. Test a simple chain, a two-node cycle, a disconnected graph, and duplicate-looking but unique prerequisite pairs. Practice explaining why a plain visited set is insufficient for directed-cycle detection.