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)