【python-leetcode210-拓扑排序】课程表Ⅱ

 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        indegrees=[0 for _ in range(numCourses)]
        adjacency=[[] for _ in range(numCourses)]
        for cur,pre in prerequisites:
            indegrees[cur]+=1
            adjacency[pre].append(cur)
        from collections import deque
        queue=deque()
        for i in range(len(indegrees)):
            if not indegrees[i]:
                queue.append(i)
        res=[]
        while queue:
            t=queue.popleft()
            res.append(t)
            numCourses-=1
            for i in adjacency[t]:
                indegrees[i]-=1
                if not indegrees[i]:
                    queue.append(i)
        if numCourses:
            return []
        else:
            return res

class Solution:                             
    def __init__(self):
        self.res=[]
    def findOrder(self, numCourses,prerequisites):
        adjacency=[[] for _ in range(numCourses)]
        flags=[0 for _ in range(numCourses)]
        for cur,pre in prerequisites:
            adjacency[pre].append(cur)
        for i in range(numCourses):
            if not self.dfs(i,adjacency,flags):
                return []
        return self.res[::-1]
    def dfs(self,i,adjacency,flags):
        #如果值为1，表明已经被访问过
        if flags[i] == 1:
            return True
        #如果值为2，表明已第二次被访问，说明有环
        if flags[i] == 2:
            return False
        flags[i]=2
        for j in adjacency[i]:
            if not self.dfs(j,adjacency,flags):
                return False
        #到这里说明所有前驱节点都访问完了    
        #并将当前节点状态置为1
        flags[i]=1
        self.res.append(i)
        return True