Course Schedule

题目描述

解题方法

  • if node v hash not been visited, mark it as 0
  • if node v is being visited, then mark it as 1, if we find a vertex marked as 1 in DFS, then there is a ring.
  • if node v has been visited, mark it as 2. if a vertex was marked as 2, then no ring contains v or its successors, we can return

Solution

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        edge_map = {}
        for pre in prerequisites:
            if pre[0] in edge_map:
                edge_map[pre[0]].append(pre[1])
            else:
                edge_map[pre[0]] = [pre[1]]
        visited = [0 for i in range(numCourses)]
        #stack = []

        def dfs(course):
            if visited[course] == 1:
                return False
            if visited[course] == 2:
                return True
            visited[course] = 1
            if course in edge_map:
                for depend in edge_map[course]:
                    if not dfs(depend):
                        return False
            visited[course] = 2
            # stack.append(course)
            return True

        for i in range(numCourses):
            if visited[i] == 0:
                if not dfs(i):
                    return False

        # stack.reverse()
        return True

Reference