MediumBlind75GraphTopological SortBFSDFS

Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. Some courses have prerequisites. Return true if you can finish all courses.

Examples

Input
numCourses = 2, prerequisites = [[1,0]]
Output
true

To take course 1 you need to finish course 0. Possible.

Input
numCourses = 2, prerequisites = [[1,0],[0,1]]
Output
false

There is a cycle: 0 -> 1 -> 0.

Constraints

  • •1 <= numCourses <= 2000
  • •0 <= prerequisites.length <= 5000
  • •prerequisites[i].length == 2
  • •0 <= ai, bi < numCourses

Approaches

Use DFS to detect cycles in the course dependency graph.

CodeT: O(V + E) | S: O(V + E)
def can_finish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    for course, prereq in prerequisites:
        graph[course].append(prereq)
    visited = [0] * numCourses
    def dfs(node):
        if visited[node] == 1:
            return True
        if visited[node] == 2:
            return False
        visited[node] = 1
        for neighbor in graph[node]:
            if dfs(neighbor):
                return True
        visited[node] = 2
        return False
    for i in range(numCourses):
        if dfs(i):
            return False
    return True

Use Kahn's algorithm for topological sorting.

CodeT: O(V + E) | S: O(V + E)
from collections import deque

def can_finish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return count == numCourses

Same topological sort with cleaner implementation.

Diagram

numCourses=4, prerequisites=[[1,0],[2,1],[3,2]] Graph: 0->1->2->3 In-degree: [0,1,1,1] Queue: [0] -> process 0, add 1 Queue: [1] -> process 1, add 2 Queue: [2] -> process 2, add 3 Order: [0,1,2,3], len=4 == 4 -> True
CodeT: O(V + E) | S: O(V + E)
from collections import deque

def can_finish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses
    for dest, src in prerequisites:
        graph[src].append(dest)
        in_degree[dest] += 1
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return len(order) == numCourses

Complexity Comparison

DFS - Cycle Detection
T: O(V + E)S: O(V + E)

Use DFS to detect cycles in the course dependency graph.

BFS - Topological Sort (Kahn's)
T: O(V + E)S: O(V + E)

Use Kahn's algorithm for topological sorting.

Optimized Kahn's Algorithm
T: O(V + E)S: O(V + E)

Same topological sort with cleaner implementation.

Common Mistakes

Not building the adjacency list correctly (reversed edges)

Using BFS without tracking in-degree

Not handling the case where all courses have prerequisites (cycle detection)

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems