Question: https://leetcode.com/problems/course-schedule-ii/
Question Name: Course Schedule II
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | class Course(object): def __init__(self): self.prerequisites = set() self.descendants = set() class Solution(object): def findOrder(self, numCourses, prerequisites): """ :type numCourses: int :type prerequisites: List[List[int]] :rtype: List[int] """ ready_to_take = {CourseID:Course() for CourseID in xrange(numCourses)} waiting_for_prerequisite = {} # Build a graph to represent the courses dependence. for course, prerequisite in prerequisites: if course in ready_to_take: waiting_for_prerequisite[course] = ready_to_take[course] del ready_to_take[course] waiting_for_prerequisite[course].prerequisites.add(prerequisite) if prerequisite in ready_to_take: ready_to_take[prerequisite].descendants.add(course) else: waiting_for_prerequisite[prerequisite].descendants.add(course) # Travel the graph to get a course schedule. courses_order = [] while len(ready_to_take) != 0: courseID, courseInfo = ready_to_take.popitem() courses_order.append(courseID) for descendant in courseInfo.descendants: waiting_for_prerequisite[descendant].prerequisites.remove(courseID) if len(waiting_for_prerequisite[descendant].prerequisites) == 0: ready_to_take[descendant] = waiting_for_prerequisite[descendant] del waiting_for_prerequisite[descendant] if len(waiting_for_prerequisite) == 0: return courses_order else: return [] |