Course Schedule

LeetCode: https://leetcode.com/problems/course-schedule/

There are numCourses courses. Given prerequisites [a, b] meaning you must take b before a, return true if you can finish all courses.

1def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
2    graph = [[] for _ in range(numCourses)]
3    for a, b in prerequisites:
4        graph[a].append(b)
5        
6    visiting = set()
7    visited = set()
8    
9    def dfs(c: int) -> bool:
10        if c in visiting:
11            return False
12        if c in visited:
13            return True
14        visiting.add(c)
15        for pre in graph[c]:
16            if not dfs(pre):
17                return False
18        visiting.remove(c)
19        visited.add(c)
20        return True
21    
22    for c in range(numCourses):
23        if not dfs(c):
24            return False
25    return True

Clone Graph

Number of Provinces

prerequisites=Array(4)

graph={ 0, 1, 2, 3 }

visiting=[]

visited=[]

Step 1 / 6

Step 1:

Build graph[a] = prerequisites of a. Use visiting to detect a cycle.

Focus: default