Lintcode 207 Course Schedule
https://leetcode.com/problems/course-schedule/description
We can follow the steps introduced in https://leetcode-solution.com/breadth-first-search to solve this problem.
- Build the graph
- Calculate the in degree count for each node
- Put all the nodes that have a 0 in degree to the queue
- Iterate through the queue until it’s empty and update
visitedandin_degreemap accordingly - At the end, check if the
visitedlength is the same as thenumCourse. It yes return true, otherwise it means there’s a loop somewhere in the graph so return false
Let’s take a look at the solution:
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
if len(prerequisites) == 0:
return True
queue = collections.deque()
visited = set()
in_degree = {i: 0 for i in range(numCourses)}
for c in prerequisites:
[ course, pre ] = c
if course in in_degree:
in_degree[course] += 1
else:
in_degree[course] = 1
graph = {i: [] for i in range(numCourses)}
for c in prerequisites:
[ course, pre ] = c
if pre in graph:
graph[pre].append(course)
else:
graph[pre] = [course]
for course, count in in_degree.items():
if count == 0:
queue.append(course)
visited.add(course)
while queue:
pre = queue.popleft()
for course in graph[pre]:
if course in visited:
continue
in_degree[course] -= 1
if in_degree[course] == 0:
queue.append(course)
visited.add(course)
return len(visited) == numCourses