Участник:Plague rat/Course Schedule

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/course-schedule/

class Solution:
    def DFSFoundCycle(self, start, nodeColors, graph):
        nodeColors[start] = 1
        for node in graph[start]:
            if nodeColors[node] == 0:
                if self.DFSFoundCycle(node, nodeColors, graph):
                    return True
            elif nodeColors[node] == 1:
                return True
        nodeColors[start] = 2
        return False
 
 
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        prerequisitesGraph = [[] for i in range(numCourses)]
        for pair in prerequisites:
            prerequisitesGraph[pair[1]].append(pair[0])
        colors = [0] * numCourses
        for i in range(numCourses):
            if self.DFSFoundCycle(i, colors, prerequisitesGraph):
                return False
        return True