There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:


Input: 2, [[1,0]] 
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished   
             course 0. So the correct course order is [0,1] .

Example 2:


Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both     
             courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. 
             So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

Note:


       The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
       You may assume that there are no duplicate edges in the input prerequisites.

Difficulty: interview

Starter code:

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        

Solutions:
class Solution:
     def findOrder(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: List[int]
         """
         n = numCourses  
         graph = {}
         for post, pre in prerequisites:
             if pre in graph:
                 graph[pre].append(post)
             else:
                 graph[pre] = [post]
         
         WHITE = 0 # never explored. NOT CHECKED
         GREY = 1 # in the stack, exploring. CHECKING
         BLACK = 2 # finished explored and we know for a fact there's no loop originated from this. CHECKED
         state = [WHITE for _ in range(0, n)]
         
         res = []
         
         def dfs(i):
             state[i] = GREY
             for child in graph.get(i, []):
                 if state[child] == GREY:
                     return False
                 elif state[child] == WHITE:
                     if not dfs(child):
                         return False
             state[i] = BLACK
             res.insert(0, i)
             return True
         
         for i in range(0, n):
             if state[i] != BLACK:
                 if not dfs(i):
                     return []
         return res


class Solution:
     def findOrder(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: List[int]
         """
         if numCourses <= 1:
             return [0]
         
         if not prerequisites:
             return [i for i in range(numCourses)]
         
         # create graph first
         graph = [[] for _ in range(numCourses)]
         for pair in prerequisites:
             x,y = pair
             graph[x].append(y)
         
         # call topo order
         visited, visiting, topo = set(), set(), []
         for i in range(numCourses):
             if i not in visited:
                 if not self.topoOrder(graph, i, visited, visiting, topo):
                     return []
         return topo
             
     def topoOrder(self, graph, start, visited, visiting, topo):
         visited.add(start)
         visiting.add(start)
         adj_verts = graph[start]
         for vert in adj_verts:
             if vert in visiting:
                 return False
             elif vert not in visited:
                 if not self.topoOrder(graph, vert, visited, visiting, topo):
                     return False
         if start in visiting:
             visiting.remove(start)
         topo.append(start)
         return True
             
             


class Solution:
     def findOrder(self,numCourses,prerequisites):
         graph=[[] for i in range(0,numCourses)];
         for edge in prerequisites:
             graph[edge[1]].append(edge[0]);
 
         #print(graph);
         mark=[0]*numCourses;
         order=[];
         for i in range(0,numCourses):
             if mark[i]==0:
                 if not self.DFS(graph,i,mark,order):
                     return [];
 
         res=[];
         for i in range(len(order)-1,-1,-1):
             res.append(order[i]);
             
         return res;
 
 
 
     def DFS(self,graph,index,mark,order):
         mark[index]=1;
         for vertex in graph[index]:
             if mark[vertex]==0:
                 if not self.DFS(graph,vertex,mark,order):
                     return False;
             elif mark[vertex]==1:
                 return False;
 
         mark[index]=2;
         order.append(index);
         return True;


class Solution:
     def findOrder(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: List[int]
         """
         nums = [[] for _ in range(numCourses)]
         du = [0] * numCourses
         for end, start in prerequisites:
             nums[start].append(end)
             du[end] += 1
         result = []
         def dfs(idx):
             du[idx] -= 1
             result.append(idx)
             for i in nums[idx]:
                 du[i] -= 1
                 if du[i] == 0:
                     dfs(i)
         for i in range(numCourses):
             if du[i] == 0:
                 dfs(i)
         if len(result) == numCourses:
             return result
         return []
 


class Solution:
     # @param {integer} numCourses
     # @param {integer[][]} prerequisites
     # @return {integer[]}
     def findOrder(self, numCourses, prerequisites):
         # use DFS to parse the course structure
         self.graph = collections.defaultdict(list) # a graph for all courses
         self.res = [] # start from empty
         for pair in prerequisites:
             self.graph[pair[0]].append(pair[1]) 
         self.visited = [0 for x in range(numCourses)] # DAG detection 
         for x in range(numCourses):
             if not self.DFS(x):
                 return []
              # continue to search the whole graph
         return self.res
     
     def DFS(self, node):
         if self.visited[node] == -1: # cycle detected
             return False
         if self.visited[node] == 1:
             return True # has been finished, and been added to self.res
         self.visited[node] = -1 # mark as visited
         for x in self.graph[node]:
             if not self.DFS(x):
                 return False
         self.visited[node] = 1 # mark as finished
         self.res.append(node) # add to solution as the course depenedent on previous ones
         return True

class Solution:
     def findOrder(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: List[int]
         """
         
         def dfs( v, edgesOut, seen, pCounts ):
             if seen[v] == 1:
                 return []
             else:
                 if pCounts[v] > 0:
                     return []
                 else:
                     seen[v] = 1
                     order = [v]
                     for e in edgesOut[v]:
                         pCounts[e] -= 1
                     for e in edgesOut[v]:
                         order += dfs( e, edgesOut, seen, pCounts )
                     return order
         
         seen = [0] * numCourses
         pCounts = [0] * numCourses
         edgesOut = [[] for __ in range(numCourses)]
         for (a,b) in prerequisites:
             edgesOut[b].append(a)
             pCounts[a] += 1
         
         order = []
         for v in range(numCourses):
             order += dfs( v, edgesOut, seen, pCounts )
         
         if len(order) < numCourses:
             return []
         else:
             return order
         
         
         
         
         
             


class Solution:
     def findOrder(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: List[int]
         """
         
         def dfs( v, edgesOut, seen, pCounts ):
             if seen[v] == 1:
                 return []
             else:
                 if pCounts[v] > 0:
                     return []
                 else:
                     seen[v] = 1
                     order = [v]
                     for e in edgesOut[v]:
                         pCounts[e] -= 1
                     for e in edgesOut[v]:
                         order += dfs( e, edgesOut, seen, pCounts )
                     return order
         
         seen = [0] * numCourses
         pCounts = [0] * numCourses
         edgesOut = [[] for __ in range(numCourses)]
         edgesIn = [[] for __ in range(numCourses)]
         for (a,b) in prerequisites:
             edgesOut[b].append(a)
             edgesIn[a].append(b)
             pCounts[a] += 1
         
         order = []
         for v in range(numCourses):
             order += dfs( v, edgesOut, seen, pCounts )
         
         if len(order) < numCourses:
             return []
         else:
             return order
         
         
         
         
         
             


class Solution:
     def findOrder(self, numCourses, prerequisites):
             # use DFS to parse the course structure
             self.graph = collections.defaultdict(list) # a graph for all courses
             self.res = [] # start from empty
             for pair in prerequisites:
                 self.graph[pair[0]].append(pair[1]) 
             self.visited = [0 for x in range(numCourses)] # DAG detection 
             for x in range(numCourses):
                 if not self.DFS(x):
                     return []
                  # continue to search the whole graph
             return self.res
         
     def DFS(self, node):
         if self.visited[node] == -1: # cycle detected
             return False
         if self.visited[node] == 1:
             return True # has been finished, and been added to self.res
         self.visited[node] = -1 # mark as visited
         for x in self.graph[node]:
             if not self.DFS(x):
                 return False
         self.visited[node] = 1 # mark as finished
         self.res.append(node) # add to solution as the course depenedent on previous ones
         return True

class Solution:
     def findOrder(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: List[int]
         """
         from collections import deque
         class Vert(object):
             def __init__(self):
                 self.visited = 0
                 self.adjList = []
                 self.invAdjList = []
                 self.inDegree = 0
                 self.outDegree = 0
         
         #initialization
         verts = []
         for _ in range(numCourses):
             verts.append(Vert())
 
         for prereq in prerequisites:
             pre = prereq[1]
             post = prereq[0]
             verts[pre].adjList.append(post)
             verts[pre].outDegree += 1
             verts[post].invAdjList.append(pre)
             verts[post].inDegree += 1
 
         #we use DFS
         #note that BFS is to preOrder what DFS is to postOrder
         coursesToLearn = deque()
 
         def visitCourse(index):
             """verts, coursesToLearn, visited"""
             if verts[index].visited == 2:
                 return 0 #返回条件1: 不必要, 只是为了不重复工作
 
             #判断已访问记号: 判断是否存在loop
             elif verts[index].visited == 1:
                 return 1# the diagram is cyclic
             
             #设置已访问记号: 判断是否存在loop
             verts[index].visited = 1
 
             # recursion主体
             for i in verts[index].adjList:
                 if visitCourse(i) == 1:
                     return 1
 
             # 返回条件2: 访问完所有children
             verts[index].visited = 2
             coursesToLearn.appendleft(index)
             return 0
         
         for i in range(numCourses):
             if verts[i].visited == 0:
                 if visitCourse(i) == 1:
                     break
         if len(coursesToLearn) == numCourses:
             return list(coursesToLearn)
         else:
             return []


class Solution:
     def findOrder(self, numCourses, prerequisites):
         graph = [[] for _ in range(numCourses)]
         visit = [0 for _ in range(numCourses)]
         result = []
         for x in prerequisites:
             graph[x[1]].append(x[0])
         print(graph)    
         def dfs(i):
             if visit[i]==-1:
                 return []
             if visit[i]==1:
                 return result
             visit[i]=-1
             for x in graph[i]:
                 if [] == dfs(x):
                     return []
             visit[i] = 1
             result.append(i)
             return result
             
         for x in range(numCourses):
             if [] == dfs(x):
                 return []
         return result[::-1]   
                 
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: List[int]
         """


from collections import defaultdict
 
 NOT_VISITED, VISITING, VISITED = 'NOT_VISITED', 'VISITING', 'VISITED'
 
 
 class Solution:
     def findOrder(self, numCourses, prerequisites):
         al = {i: [] for i in range(numCourses)}
         for cn, pn in prerequisites:
             al[cn].append(pn)
         vst = defaultdict(lambda: NOT_VISITED)
         srt = []
 
         def dfs(cn):
             '''
             Adds to topo sort if no cycle found
             '''
             if vst[cn] == VISITING:
                 return False
             elif vst[cn] == VISITED:
                 return True
 
             vst[cn] = VISITING
 
             for pre in al[cn]:
                 if not dfs(pre):
                     return False  # cycle found, no such topo sort
 
             vst[cn] = VISITED
             srt.append(cn)
 
             return True
 
         for cn in range(numCourses):
             if not dfs(cn):
                 return []  # cycle found, no such topo sort
 
         return srt


class Solution:
     def findOrder(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: List[int]
         """
         graph=[[]for _ in range(numCourses)]
         degree=[0 for _ in range(numCourses)]
         
         for f,i  in prerequisites:
             degree[f]+=1
             graph[i].append(f)
         res=[]
         print(degree)
         now_can_learn=[j for j in range(numCourses) if degree[j] == 0]
         while (len(now_can_learn)>0):
             curr=now_can_learn.pop()
             res.append(curr)
             for j in graph[curr]:
                 degree[j] -=1
                 if degree[j]==0:
                     now_can_learn.append(j)
         return res if len(res)==numCourses else []
         
         
                         


import queue
 
 class Solution:
     def findOrder(self, numCourses, prerequisites):
         """
         :type numCourses: int
         :type prerequisites: List[List[int]]
         :rtype: List[int]
         """
         graph = {}
         for course, prereq in prerequisites:
             graph[prereq] = graph[prereq] + [course] if prereq in graph else [course]
         degree = [0] * numCourses
         for course, _ in prerequisites:
             degree[course] += 1
         q = queue.Queue()
         for i in range(numCourses):
             if degree[i] == 0:
                 q.put(i)
         res = []
         while not q.empty():
             pre = q.get()
             if pre in graph:
                 for course in graph[pre]:
                     degree[course] -= 1
                     if degree[course] == 0:
                         q.put(course)
             res.append(pre)
         return res if len(res) == numCourses else []