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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Directed graphs

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

Solutions:
class Solution:

	def findOrder(self, numCourses, prerequisites):
		n = numCourses
		graph = {}
		for (post, pre) in prerequisites:
			if pre in graph:
				graph[pre].append(post)
			else:
				graph[pre] = [post]
		WHITE = 0
		GREY = 1
		BLACK = 2
		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):
		if numCourses <= 1:
			return [0]
		if not prerequisites:
			return [i for i in range(numCourses)]
		graph = [[] for _ in range(numCourses)]
		for pair in prerequisites:
			(x, y) = pair
			graph[x].append(y)
		(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])
		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):
		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:

	def findOrder(self, numCourses, prerequisites):
		self.graph = collections.defaultdict(list)
		self.res = []
		for pair in prerequisites:
			self.graph[pair[0]].append(pair[1])
		self.visited = [0 for x in range(numCourses)]
		for x in range(numCourses):
			if not self.DFS(x):
				return []
		return self.res

	def DFS(self, node):
		if self.visited[node] == -1:
			return False
		if self.visited[node] == 1:
			return True
		self.visited[node] = -1
		for x in self.graph[node]:
			if not self.DFS(x):
				return False
		self.visited[node] = 1
		self.res.append(node)
		return True


class Solution:

	def findOrder(self, numCourses, prerequisites):

		def dfs(v, edgesOut, seen, pCounts):
			if seen[v] == 1:
				return []
			elif 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):
		from collections import deque

		class Vert(object):

			def __init__(self):
				self.visited = 0
				self.adjList = []
				self.invAdjList = []
				self.inDegree = 0
				self.outDegree = 0
		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
		coursesToLearn = deque()

		def visitCourse(index):
			if verts[index].visited == 2:
				return 0
			elif verts[index].visited == 1:
				return 1
			verts[index].visited = 1
			for i in verts[index].adjList:
				if visitCourse(i) == 1:
					return 1
			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]


class Solution:

	def findOrder(self, numCourses, prerequisites):
		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 []