[算法] Course Schedule

Question
Course Schedule

Question Description

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example

Example 1:

Input: n = 2, prerequisites = [[1,0]] 
Output: true

Example 2:

Input: n = 2, prerequisites = [[1,0],[0,1]] 
Output: false

Language
Python 3

Data structure description
""" @param: numCourses: a total of n courses @param: prerequisites: a list of prerequisite pairs @return: true if can finish all courses or false """

Solution
class Solution: def canFinish(self, numCourses, prerequisites): edges = {n: [] for n in range(numCourses)} inDegree = [0 for i in range(numCourses)] for (x, y) in prerequisites: edges[y].append(x) inDegree[x] += 1 queue = collections.deque([]) count = 0 for i in range(numCourses): if inDegree[i] == 0: queue.append(i) while queue: node = queue.popleft() count += 1 for e in edges[node]: inDegree[e] -= 1 if inDegree[e] == 0: queue.append(e) if count == numCourses: return True return False

Reference Link
https://www.lintcode.com/problem/course-schedule/description