from collections import defaultdict
import Queue
class Solution:
"""
@param: numCourses: a total of n courses
@param: prerequisites: a list of prerequisite pairs
@return: true if can finish all courses or false
"""
def canFinish(self, numCourses, prerequisites):
edges = defaultdict(list)
degree = defaultdict(int)
for pre, course in prerequisites:
degree[pre] += 1
edges[course].append(pre)
queue = Queue.Queue()
for i in range(numCourses):
if degree[i] == 0:
queue.put(i)
count = 0
while not queue.empty():
course = queue.get()
count += 1
for post in edges[course]:
degree[post] -= 1
if degree[post] == 0:
queue.put(post)
return count == numCourses