Question: https://leetcode.com/problems/course-schedule/
Question Name: Course Schedule
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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | class Solution(object): def _hasLoop(self, courseID, adjacencySet, reachableNodes, currentPath): """ :type numCourses: int :type adjacencySet: List[set(int)] :type: reachableNodes: mutable, set(int) :type: current_path: mutalbe, set(int) :rtype: bool """ if courseID in currentPath: return True currentPath.add(courseID) reachableNodes.add(courseID) for prerequisite in adjacencySet[courseID]: if self._hasLoop(prerequisite, adjacencySet, reachableNodes, currentPath): return True currentPath.remove(courseID) return False def _buildAdjacencySet(self, numCourses, prerequisites): """ :type numCourses: int :type prerequisites: List[List[int]] :rtype: List[set(int)] """ adj_set = [set() for _ in xrange(numCourses)] for prerequisite in prerequisites: adj_set[prerequisite[0]].add(prerequisite[1]) return adj_set def canFinish(self, numCourses, prerequisites): """ :type numCourses: int :type prerequisites: List[List[int]] :rtype: bool """ # Find out the courses, which are not prerequisite of others. is_prerequisite = [False for _ in xrange(numCourses)] for prerequisite in prerequisites: is_prerequisite[prerequisite[1]] = True adjacency_set = self._buildAdjacencySet(numCourses, prerequisites) is_doable = [False for _ in xrange(numCourses)] for courseID in xrange(numCourses): if is_prerequisite[courseID]: continue # Check whether it is possible to finish this course. # If it is, all its direct/indirect prerequisites are also doable. reachable_nodes = set() current_path = set() if self._hasLoop(courseID, adjacency_set, reachable_nodes, current_path): return False for courseID in reachable_nodes: is_doable[courseID] = True return all(is_doable) |