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

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

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

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 topologicalSort(self, start, visited, order, graph):
        visited[start] = True
        for node in graph[start]:
            if not visited[node]:
                self.topologicalSort(node, visited, order, graph)
        order.append(start)
 
 
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        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 []
 
        visited = [False] * numCourses
        order = []
        for i in range(numCourses):
            if not visited[i]:
                self.topologicalSort(i, visited, order, prerequisitesGraph)
        return reversed(order)