💬 Discord
Sign In
NeetCode #575LC-207MediumGraphsBlind 75NC 150NC 250
← Back to All Problems

#575 · #207 · Course Schedule(课程表)

📌 Problem Statement & Constraints

There are numCourses courses labelled 0..numCourses-1. Given prerequisites where prerequisites[i] = [a, b] means b must be taken before a, return whether all courses can be finished. Constraints: 1 <= numCourses <= 2000, 0 <= prerequisites.length <= 5000.

💡 Core Algorithmic Approaches

  1. The prerequisites form a directed graph; the courses can all be finished exactly when the graph has no cycle.
  2. Kahn's algorithm: repeatedly remove nodes with in-degree 0 and count how many are removed.
  3. If the count equals numCourses, there is no cycle.
  4. The DFS alternative uses three colours (white/grey/black) and reports a cycle when a grey node is revisited.

💻 Benchmark Python3 Implementation

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        from collections import defaultdict, deque
        g = defaultdict(list)
        indeg = [0] * numCourses
        for a, b in prerequisites:         # b -> a
            g[b].append(a)
            indeg[a] += 1
        q = deque(i for i in range(numCourses) if indeg[i] == 0)
        done = 0
        while q:
            node = q.popleft()
            done += 1
            for nxt in g[node]:
                indeg[nxt] -= 1
                if indeg[nxt] == 0:
                    q.append(nxt)
        return done == numCourses          # all nodes removed -> acyclic


# DFS colouring variant
class Solution2:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        from collections import defaultdict
        g = defaultdict(list)
        for a, b in prerequisites:
            g[b].append(a)
        state = [0] * numCourses           # 0 = unvisited, 1 = on stack, 2 = done

        def dfs(node: int) -> bool:
            if state[node] == 1:
                return False               # back edge -> cycle
            if state[node] == 2:
                return True
            state[node] = 1
            for nxt in g[node]:
                if not dfs(nxt):
                    return False
            state[node] = 2
            return True

        return all(dfs(i) for i in range(numCourses))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(V + E): each node and edge is processed once.
💾 Space Complexity
O(V + E) for the graph and O(V) for the bookkeeping.

⚠️ Interview Pitfalls & Follow-ups

  • Building the edge in the wrong direction: [a, b] means b before a, so the edge is b -> a.
  • Comparing the removed count against len(prerequisites): the count is of nodes, so it is compared with numCourses.
  • Using a single visited flag in the DFS variant: a node on the current path must be distinguished from one fully processed -- hence three states.
  • Assuming the graph is connected: it may be a forest, so all nodes must be started.