Given a Directed Acyclic Graph (DAG) with V vertices and E edges, Find any Topological Sorting of that Graph.
Example 1:
Input:
Output:
1
Explanation:
The output 1 denotes that the order is
valid. So, if you have, implemented
your function correctly, then output
would be 1 for all test cases.
One possible Topological order for the
graph is 3, 2, 1, 0.
Example 2:
Input:
Output:
1
Explanation:
The output 1 denotes that the order is
valid. So, if you have, implemented
your function correctly, then output
would be 1 for all test cases.
One possible Topological order for the
graph is 5, 4, 2, 1, 3, 0.
Your Task:
You don't need to read input or print anything. Your task is to complete the function topoSort()  which takes the integer V denoting the number of vertices and adjacency list as input parameters  and returns an array consisting of the vertices in Topological order. As there are multiple Topological orders possible, you may return any of them. If your returned topo sort is correct then the console output will be 1 else 0.
Expected Time Complexity: O(V + E).
Expected Auxiliary Space: O(V).
Constraints:
2  ≤  V  ≤ 10^{4}
1  ≤  E  ≤  (N*(N-1))/2

Difficulty: MEDIUM
Tags: Graph algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(V + E).
Expected Auxiliary Space: O(V).

Starter code:
class Solution:

    

    #Function to return list containing vertices in Topological order.

    def topoSort(self, V, adj):

        # Code here



Solutions:
from collections import deque

class Solution:

	def topoSort(self, V, adj):
		ind = [0 for i in range(V)]
		for i in range(V):
			for nei in adj[i]:
				ind[nei] += 1
		q = deque()
		for i in range(V):
			if ind[i] == 0:
				q.append(i)
		res = []
		while len(q) > 0:
			node = q.popleft()
			res.append(node)
			for nei in adj[node]:
				ind[nei] -= 1
				if ind[nei] == 0:
					q.append(nei)
		return res


import collections

class Solution:

	def topoSort(self, V, adj):
		vis = [0] * V
		stack = []
		res = []

		def dfs(node):
			vis[node] = 1
			for i in adj[node]:
				if vis[i] == 0:
					dfs(i)
			stack.append(node)
		for i in range(V):
			if vis[i] == 0:
				dfs(i)
		res = stack[::-1]
		return res


import collections

class Solution:

	def topoSort(self, V, adj):
		res = []
		ind = [0] * V
		for i in range(V):
			for j in adj[i]:
				ind[j] += 1
		q = collections.deque()
		for i in range(V):
			if ind[i] == 0:
				q.append(i)
		while q:
			first = q.pop()
			res.append(first)
			for i in adj[first]:
				ind[i] -= 1
				if ind[i] == 0:
					q.append(i)
		return res


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		indegree = [0 for i in range(V)]
		q = deque()
		res = []
		for i in range(len(adj)):
			for j in adj[i]:
				indegree[j] += 1
		for i in range(V):
			if indegree[i] == 0:
				q.append(i)
		while len(q) > 0:
			cur = q.popleft()
			res.append(cur)
			for i in adj[cur]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.append(i)
		return res


class Solution:

	def visit(self, cur_node, adj_node, seen, res):
		for adj_node in adj[cur_node]:
			if adj_node not in seen:
				seen.add(adj_node)
				self.visit(adj_node, adj, seen, res)
		res.append(cur_node)

	def topoSort(self, V, adj):
		res = []
		seen = set()
		for node in range(V):
			if node not in seen:
				seen.add(node)
				self.visit(node, adj, seen, res)
		return list(reversed(res))


class Solution:

	def topoSort(self, v, adj):
		st = []
		visited = [False] * (v + 1)
		for i in range(v):
			if visited[i] == False:
				self.dfsRec(adj, visited, i, st)
		ans = st[::-1]
		return ans

	def dfsRec(self, arr, visited, s, st):
		visited[s] = True
		for i in arr[s]:
			if visited[i] == False:
				self.dfsRec(arr, visited, i, st)
		st.append(s)


class Solution:

	def topoSort(self, V, adj):
		indegree = [0 for _ in range(V)]
		for x in range(len(adj)):
			for i in adj[x]:
				indegree[i] += 1
		queue = []
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
		stack = []
		while len(queue) != 0:
			temp = queue.pop(0)
			for x in adj[temp]:
				indegree[x] -= 1
				if indegree[x] == 0:
					queue.append(x)
			stack.append(temp)
		return stack[:]


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		inedge = [0 for i in range(V)]
		queue = deque()
		for i in range(V):
			for child in adj[i]:
				inedge[child] += 1
		for i in range(V):
			if inedge[i] == 0:
				queue.append(i)
		res = []
		while queue:
			size = len(queue)
			while size:
				popped = queue.popleft()
				res.append(popped)
				for child in adj[popped]:
					inedge[child] -= 1
					if inedge[child] == 0:
						queue.append(child)
				size -= 1
		return res


class Solution:

	def topoSort(self, V, adj):

		def topoSortUtil(node):
			visited[node] = 1
			for x in adj[node]:
				if not visited[x]:
					topoSortUtil(x)
			stack.append(node)
		visited = [0 for _ in range(V)]
		stack = []
		for i in range(V):
			if not visited[i]:
				topoSortUtil(i)
		res = []
		while len(stack) != 0:
			res.append(stack.pop())
		return res[:]


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		visited = set()
		q = deque()

		def dfs(node):
			visited.add(node)
			for nei in adj[node]:
				if nei not in visited:
					dfs(nei)
			q.append(node)
		for i in range(V):
			if i not in visited:
				dfs(i)
		result = []
		for node in range(V):
			result.append(q.pop())
		return result


class Solution:

	def toposort(self, indegree, V, adj, ans):
		queue = []
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
		while queue:
			node = queue.pop(0)
			ans.append(node)
			for neighbor in adj[node]:
				indegree[neighbor] -= 1
				if indegree[neighbor] == 0:
					queue.append(neighbor)

	def topoSort(self, V, adj):
		indegree = [0] * V
		ans = []
		for i in range(V):
			for j in adj[i]:
				indegree[j] += 1
		self.toposort(indegree, V, adj, ans)
		return ans


class Solution:

	def topoSort(self, v, adj):
		ind = [0] * v
		for i in adj:
			for j in i:
				ind[j] += 1
		(q, ans) = ([], [])
		for i in range(v):
			if ind[i] == 0:
				q.append(i)
		while len(q) > 0:
			u = q.pop(0)
			ans.append(u)
			for i in adj[u]:
				if ind[i] == 1:
					q.append(i)
				ind[i] -= 1
		return ans


import queue

class Solution:

	def topoSort(self, v, adjList):
		s = queue.Queue()
		indegree = [0] * v
		for i in range(v):
			for j in adjList[i]:
				indegree[j] += 1
		for i in range(v):
			if indegree[i] == 0:
				s.put(i)
		res = []
		while not s.empty():
			curr = s.get()
			res.append(curr)
			for t in adjList[curr]:
				indegree[t] -= 1
				if indegree[t] == 0:
					s.put(t)
		return res


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		queue = []
		ans = []
		degree = [0 for x in range(V)]
		for x in range(V):
			for y in adj[x]:
				degree[y] += 1
		for x in range(V):
			if degree[x] == 0:
				queue.append(x)
		while queue:
			curr = queue.pop(0)
			ans.append(curr)
			for x in adj[curr]:
				degree[x] -= 1
				if degree[x] == 0:
					queue.append(x)
		return ans


class Solution:

	def topoSort(self, V, adj):
		ans = []
		v = set()

		def dfs(node):
			v.add(node)
			for x in adj[node]:
				if x not in v:
					dfs(x)
			ans.append(node)
		for x in range(V):
			if x not in v:
				dfs(x)
		return ans[::-1]


class Solution:

	def topoSort(self, V, adj):
		return topological_sort(adj)

def topological_sort(G):

	def visit(G, visited, parent, u, s):
		visited[u] = 'g'
		for v in G[u]:
			if visited[v] == 'w':
				parent[v] = u
				visit(G, visited, parent, v, s)
			if visited[v] == 'g':
				raise ValueError('Not a DAG')
		visited[u] = 'b'
		s.append(u)
	n = len(G)
	visited = ['w'] * n
	parent = [None] * n
	s = []
	for u in range(n):
		if visited[u] == 'w':
			visit(G, visited, parent, u, s)
	s.reverse()
	return s


class Solution:

	def topoSort(self, V, adj):
		visited = [False for i in range(V)]
		indegree = [0 for i in range(V)]
		for i in range(V):
			for child in adj[i]:
				indegree[child] += 1
		queue = []
		for i in range(0, len(indegree)):
			if indegree[i] == 0:
				queue.append(i)
		topo = []
		while queue:
			node = queue.pop(0)
			topo.append(node)
			for child in adj[node]:
				indegree[child] = indegree[child] - 1
				if indegree[child] == 0:
					queue.append(child)
		return topo


class Solution:

	def topoSort(self, V, adj):
		visited = [False for i in range(V)]
		stack = []
		for i in range(V):
			if visited[i] == False:
				self.dfs(i, visited, stack)
		ans = []
		while stack:
			node = stack.pop(0)
			ans.append(node)
		return ans

	def dfs(self, src, visited, stack):
		visited[src] = True
		for childs in adj[src]:
			if visited[childs] == False:
				self.dfs(childs, visited, stack)
		stack.append(childs)

	def topoSort(self, V, adj):
		visited = [False for i in range(V)]
		indegree = [0 for i in range(V)]
		for i in range(V):
			for k in adj[i]:
				indegree[k] += 1
		queue = []
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
		topo = []
		while queue:
			source = queue.pop()
			topo.append(source)
			for childs in adj[source]:
				indegree[childs] = indegree[childs] - 1
				if indegree[childs] == 0:
					queue.append(childs)
		return topo


class Solution:

	def topoSort(self, V, adj):
		order = []
		visited = set()
		for i in range(V):
			self.dfs(i, order, visited, adj)
		return order[::-1]

	def dfs(self, node, order, visited, adj):
		if node in visited:
			return
		for i in adj[node]:
			self.dfs(i, order, visited, adj)
		order.append(node)
		visited.add(node)


class Solution:

	def topoSort(self, V, adj):
		n = V
		indeg = [0] * V
		for i in adj:
			for j in i:
				indeg[j] += 1
		q = []
		for i in range(V):
			if indeg[i] == 0:
				q.append(i)
		z = 0
		r = []
		while len(q) != 0:
			x = q.pop(0)
			r.append(x)
			for i in adj[x]:
				indeg[i] -= 1
				if indeg[i] == 0:
					q.append(i)
			z += 1
		return r


class Solution:

	def topoSort(self, V, adj):
		indgree = [0] * V
		q = []
		for i in range(V):
			for n in adj[i]:
				indgree[n] += 1
		for i in range(V):
			if indgree[i] == 0:
				q.append(i)
		topo = []
		while q:
			node = q.pop(0)
			topo.append(node)
			for n in adj[node]:
				indgree[n] -= 1
				if indgree[n] == 0:
					q.append(n)
		return topo


class Solution:

	def f(self, sv, visited, adj, li):
		visited[sv] = True
		for neighbour in adj[sv]:
			if visited[neighbour] == False:
				self.f(neighbour, visited, adj, li)
		li.append(sv)

	def topoSort(self, V, adj):
		li = []
		visited = [False] * V
		for i in range(V):
			if visited[i] == False:
				self.f(i, visited, adj, li)
		li.reverse()
		return li


class Solution:

	def topoSort(self, V, adj):
		inorder = [0 for i in range(V)]
		for i in range(V):
			for v in adj[i]:
				inorder[v] = inorder[v] + 1
		queue = []
		ans = []
		for i in range(V):
			if inorder[i] == 0:
				queue.append(i)
		while queue:
			child = queue.pop(0)
			ans.append(child)
			for u in adj[child]:
				inorder[u] = inorder[u] - 1
				if inorder[u] == 0:
					queue.append(u)
		return ans


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		top_stack = deque()
		visited = [False for i in range(V)]

		def rec_func(visited, top_stack, adj, i):
			visited[i] = True
			neighbours = adj[i]
			for n in neighbours:
				if not visited[n]:
					rec_func(visited, top_stack, adj, n)
			top_stack.append(i)
			return
		for i in range(V):
			if not visited[i]:
				rec_func(visited, top_stack, adj, i)
		output = []
		while len(top_stack) > 0:
			output.append(top_stack.pop())
		return output


class Solution:

	def dfs(self, node, adj, stack, visited):
		visited[node] = 1
		for nei in adj[node]:
			if visited[nei] == 0:
				self.dfs(nei, adj, stack, visited)
		stack.append(node)

	def topoSort(self, V, adj):
		visited = [0] * V
		stack = []
		for i in range(V):
			if visited[i] == 0:
				self.dfs(i, adj, stack, visited)
		return stack[::-1]


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		q = deque()
		temp = []
		in_deg = [0] * V
		for i in range(V):
			for j in adj[i]:
				in_deg[j] += 1
		for i in range(V):
			if in_deg[i] == 0:
				q.append(i)
		while q:
			curr = q.popleft()
			temp.append(curr)
			for i in adj[curr]:
				in_deg[i] -= 1
				if in_deg[i] == 0:
					q.append(i)
		return temp


class Solution:

	def topoSort(self, V, adj):
		indegree = [0] * V
		queue = []
		stack = []
		for i in range(V):
			for j in adj[i]:
				indegree[j] += 1
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
		while queue:
			x = queue.pop(0)
			stack.append(x)
			for i in adj[x]:
				indegree[i] -= 1
				if indegree[i] == 0:
					queue.append(i)
		return stack


class Solution:

	def topoSort(self, V, adj):
		stack = []
		vis = [0 for i in range(V)]

		def dfs(node):
			if vis[node] == 1:
				return
			else:
				vis[node] = 1
				for i in adj[node]:
					if vis[i] == 0:
						dfs(i)
				stack.append(node)
		for i in range(V):
			if vis[i] == 0:
				dfs(i)
		stack.reverse()
		return stack


class Solution:

	def topoSort(self, V, adj):
		visited = [0] * V
		stack = []

		def DFS(x):
			visited[x] = 1
			for i in adj[x]:
				if visited[i] == 0:
					DFS(i)
			stack.append(x)
		for i in range(V):
			if visited[i] == 0:
				DFS(i)
		ans = []
		while stack:
			ans.append(stack.pop())
		return ans


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		ts = []
		q = deque()
		indeg = [0] * V
		for cur_adj in adj:
			for vert in cur_adj:
				indeg[vert] += 1

		def DFSTopo(vert):
			ts.append(vert)
			indeg[vert] = -1
			for ele in adj[vert]:
				indeg[ele] -= 1
				if indeg[ele] == 0:
					DFSTopo(ele)
		for i in range(len(indeg)):
			if indeg[i] == 0:
				DFSTopo(i)
		return ts


import collections

class Solution:

	def topoSort(self, V, adj):
		in_deg = [0 for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				in_deg[j] += 1
		ans = []
		q = collections.deque()
		for i in range(V):
			if in_deg[i] == 0:
				q.append(i)
		while q:
			node = q.popleft()
			ans.append(node)
			for i in adj[node]:
				in_deg[i] -= 1
				if in_deg[i] == 0:
					q.append(i)
		return ans


class Solution:

	def topoSort(self, V, adj):
		result = []
		indegrees = [0] * V
		for u in range(V):
			for v in adj[u]:
				indegrees[v] += 1
		q = []
		for u in range(V):
			if indegrees[u] == 0:
				q.append(u)
		while q:
			u = q.pop(0)
			result.append(u)
			for v in adj[u]:
				indegrees[v] -= 1
				if indegrees[v] == 0:
					q.append(v)
		if len(result) != V:
			return []
		return result


class Solution:

	def topoSort(self, V, adj):
		result = []
		inDegrees = [0] * V
		for u in range(V):
			for v in adj[u]:
				inDegrees[v] += 1
		queue = []
		for u in range(V):
			if inDegrees[u] == 0:
				queue.append(u)
		while queue:
			u = queue.pop(0)
			result.append(u)
			for v in adj[u]:
				inDegrees[v] -= 1
				if inDegrees[v] == 0:
					queue.append(v)
		if len(result) != V:
			return []
		return result


class Solution:

	def topoSort(self, V, adj):
		visited = [False] * V
		res = []

		def DFS(node, adj, visited, res):
			visited[node] = True
			for i in adj[node]:
				if visited[i] == 0:
					DFS(i, adj, visited, res)
			res.append(node)
		for i in range(V):
			if visited[i] == False:
				DFS(i, adj, visited, res)
		return res[::-1]


class Solution:

	def topoSort(self, V, adj):
		visited = [False] * V
		topo = []

		def dfs(u, visited, topo):
			if visited[u]:
				return
			visited[u] = True
			for v in adj[u]:
				dfs(v, visited, topo)
			topo.append(u)
		for i in range(V):
			dfs(i, visited, topo)
		topo.reverse()
		return topo


class Solution:

	def topoSort(self, V, adj):
		d = {i: [] for i in range(V)}
		visited = {i: False for i in range(V)}
		for (ind, i) in enumerate(adj):
			d[ind] += i
		q = []

		def dfs(node):
			if visited[node]:
				return
			visited[node] = True
			for i in d[node]:
				dfs(i)
			q.append(node)
		for i in range(V):
			dfs(i)
		return q[::-1]


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		queue = deque()
		indegree = [0] * V
		result = []
		for node in range(V):
			for adjNode in adj[node]:
				indegree[adjNode] += 1
		for (index, value) in enumerate(indegree):
			if value == 0:
				queue.append(index)
		while queue:
			node = queue.popleft()
			result.append(node)
			for adjNode in adj[node]:
				indegree[adjNode] -= 1
				if indegree[adjNode] == 0:
					queue.append(adjNode)
		return result


class Solution:

	def topoSort(self, V, adj):
		stack = []
		indegree = [0] * V
		result = []
		for node in range(V):
			for adjNode in adj[node]:
				indegree[adjNode] += 1
		for (index, value) in enumerate(indegree):
			if value == 0:
				stack.append(index)
		while stack:
			node = stack.pop()
			result.append(node)
			for adjNode in adj[node]:
				indegree[adjNode] -= 1
				if indegree[adjNode] == 0:
					stack.append(adjNode)
		return result


class Solution:

	def topoSort(self, V, adj):
		stack = []
		visited = [False] * V

		def dfs(vertex):
			visited[vertex] = True
			for neighbor in adj[vertex]:
				if not visited[neighbor]:
					dfs(neighbor)
			stack.append(vertex)
		for i in range(V):
			if not visited[i]:
				dfs(i)
		return stack[::-1]


class Solution:

	def dfs(self, node, cache, adj, stack):
		cache[node] = 1
		for neighbour in adj[node]:
			if not cache[neighbour]:
				self.dfs(neighbour, cache, adj, stack)
		stack.append(node)

	def topoSort(self, V, adj):
		stack = []
		cache = [0] * V
		for i in range(V):
			if not cache[i]:
				self.dfs(i, cache, adj, stack)
		return stack[::-1]


class Solution:

	def helper(self, index, visited, stack, adj):
		visited[index] = 1
		for innerindex in adj[index]:
			if visited[innerindex] == 0:
				self.helper(innerindex, visited, stack, adj)
		stack.insert(0, index)
		return stack

	def topoSort(self, V, adj):
		visited = [0] * V
		stack = []
		for index in range(V):
			if visited[index] == 0:
				stack = self.helper(index, visited, stack, adj)
		return stack


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		indegree = [0] * V
		for i in range(V):
			for adj_node in adj[i]:
				indegree[adj_node] += 1
		q = deque()
		for i in range(len(indegree)):
			if indegree[i] == 0:
				q.append(i)
		final = []
		while q:
			z = q.popleft()
			final.append(z)
			for adj_node in adj[z]:
				indegree[adj_node] -= 1
				if indegree[adj_node] == 0:
					q.append(adj_node)
		return final


from collections import deque

class Solution:

	def topoSort(self, V, adj):

		def dfs(node, adj, vis, stack):
			vis[node] = 1
			for adj_node in adj[node]:
				if vis[adj_node] == -1:
					dfs(adj_node, adj, vis, stack)
			stack.append(node)
		vis = [-1] * V
		stack = []
		for i in range(V):
			if vis[i] == -1:
				dfs(i, adj, vis, stack)
		return stack[::-1]


class Solution:

	def topoSort(self, V, adj):
		res = []
		indegree = [0] * V
		queue = []
		for i in range(V):
			for nei in adj[i]:
				indegree[nei] += 1
		for i in range(len(indegree)):
			if indegree[i] == 0:
				queue.append(i)
		while queue:
			node = queue.pop(0)
			res.append(node)
			for nei in adj[node]:
				indegree[nei] -= 1
				if indegree[nei] == 0:
					queue.append(nei)
		return res


class Solution:

	def topoSort(self, V, adj):
		res = []
		stack = []
		visited = set()
		for i in range(V):
			if i not in visited:
				self.dfs(i, adj, visited, stack)
		for i in range(V):
			res.append(stack.pop())
		return res

	def dfs(self, node, adj, visited, stack):
		visited.add(node)
		for nei in adj[node]:
			if nei not in visited:
				self.dfs(nei, adj, visited, stack)
		stack.append(node)


class Solution:

	def findTopoSort(self, node, vis, adj, st):
		vis[node] = 1
		for it in adj[node]:
			if vis[it] == 0:
				self.findTopoSort(it, vis, adj, st)
		st.append(node)

	def topoSort(self, V, adj):
		(st, vis) = ([], [0] * V)
		for i in range(V):
			if vis[i] == 0:
				self.findTopoSort(i, vis, adj, st)
		(topo, ind) = ([0] * V, 0)
		while st:
			topo[ind] = st.pop()
			ind += 1
		return topo


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		(topo, indegree) = ([0] * N, [0] * N)
		for i in range(N):
			for it in adj[i]:
				indegree[it] += 1
		q = deque()
		for i in range(N):
			if indegree[i] == 0:
				q.append(i)
		(cnt, ind) = (0, 0)
		while q:
			node = q.popleft()
			topo[ind] = node
			(ind, cnt) = (ind + 1, cnt + 1)
			for it in adj[node]:
				indegree[it] -= 1
				if indegree[it] == 0:
					q.append(it)
		return topo


import queue

class Solution:

	def topoSort(self, V, adj):
		inorder = [0 for _ in range(V)]
		sorted_list = []
		for node in adj:
			for neighbor in node:
				inorder[neighbor] += 1
		q = queue.Queue()
		for (no, value) in enumerate(inorder):
			if value is 0:
				q.put(no)
		while not q.empty():
			node = q.get()
			sorted_list.append(node)
			for neighbors in adj[node]:
				inorder[neighbors] -= 1
				if inorder[neighbors] is 0:
					q.put(neighbors)
		return sorted_list


class Solution:

	def dfs(self, node, visit, stack, adj):
		visit[node] = 1
		for it in adj[node]:
			if not visit[it]:
				self.dfs(it, visit, stack, adj)
		stack.append(node)

	def topoSort(self, V, adj):
		visit = {i: 0 for i in range(V)}
		stack = []
		for i in range(V):
			if not visit[i]:
				self.dfs(i, visit, stack, adj)
		res = []
		while stack:
			res.append(stack.pop())
		return res


from queue import Queue

class Solution:

	def topoSort(self, V, adj):
		inDegree = [0 for i in range(V)]
		que = Queue()
		for u in range(V):
			for v in adj[u]:
				inDegree[v] += 1
		res = []
		for i in range(V):
			if inDegree[i] == 0:
				que.put(i)
		topBFS(inDegree, que, adj, res)
		return res

def topBFS(inDegree, que, adj, res):
	while que.empty() == False:
		u = que.get()
		res.append(u)
		for i in adj[u]:
			inDegree[i] -= 1
			if inDegree[i] == 0:
				que.put(i)
	return res


class Solution:

	def topoSort(self, V, adj):
		visited = [False for i in range(V)]
		res = []
		for i in range(V):
			if visited[i] == False:
				topDFS(i, adj, visited, res)
		return res[::-1]

def topDFS(sv, adj, visited, res):
	visited[sv] = True
	for i in adj[sv]:
		if visited[i] == False:
			topDFS(i, adj, visited, res)
	res.append(sv)


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		q = deque([])
		n = len(adj)
		inorder = [0] * n
		ans = []
		for i in adj:
			for j in i:
				inorder[j] += 1
		for i in range(n):
			if inorder[i] == 0:
				q.append(i)
		while q:
			ver = q.popleft()
			ans.append(ver)
			for i in adj[ver]:
				inorder[i] -= 1
				if inorder[i] == 0:
					q.append(i)
		return ans


class Solution:

	def topoSort(self, V, adj):
		inDegree = [0] * V
		visited = [0] * V
		for x in adj:
			for i in x:
				inDegree[i] += 1
		res = []
		queue = []
		for i in range(V):
			if inDegree[i] == 0:
				queue.append(i)
		while len(queue) > 0:
			node = queue.pop(0)
			res.append(node)
			visited[node] = 1
			for i in adj[node]:
				if visited[i] == 0:
					inDegree[i] -= 1
					if inDegree[i] == 0:
						queue.append(i)
		return res


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		indegree = [0] * V
		for node in range(V):
			for vertice in adj[node]:
				indegree[vertice] += 1
		q = deque()
		for node in range(V):
			if indegree[node] == 0:
				q.append(node)
		ans = []
		while q:
			node = q.popleft()
			ans.append(node)
			for vertice in adj[node]:
				indegree[vertice] -= 1
				if indegree[vertice] == 0:
					q.append(vertice)
		return ans


class Solution:

	def topoSort(self, V, adj):
		stack = []
		n = len(adj)
		vis = [0] * n

		def dfs(node):
			vis[node] = 1
			for i in adj[node]:
				if vis[i] == 0:
					dfs(i)
			stack.append(node)
		for i in range(n):
			if vis[i] == 0:
				dfs(i)
		return stack[::-1]


from queue import Queue

class Solution:

	def topoSort(self, V, adj):
		q = Queue()
		lis = []
		dic = {}
		for i in range(V):
			dic[i] = 0
		for i in range(V):
			for node in adj[i]:
				dic[node] += 1
		for key in range(V):
			if dic[key] == 0:
				q.put(key)
		while not q.empty():
			node = q.get()
			lis.append(node)
			for x in adj[node]:
				dic[x] -= 1
				if dic[x] == 0:
					q.put(x)
		return lis


class Solution:

	def topoSort(self, V, adj):
		lis = []
		vis = [0] * V
		for i in range(V):
			if vis[i] == 0:
				self.dfs(i, V, adj, vis, lis)
		j = reversed(lis)
		return list(j)

	def dfs(self, node, V, adj, vis, lis):
		vis[node] = 1
		for x in adj[node]:
			if vis[x] == 0:
				self.dfs(x, V, adj, vis, lis)
		lis.append(node)


class Solution:

	def topoSort(self, V, adj):
		in_degree = [0] * V
		for i in range(V):
			for j in adj[i]:
				in_degree[j] += 1
		queue = []
		for i in range(V):
			if in_degree[i] == 0:
				queue.append(i)
		ans = []
		while queue:
			u = queue.pop(0)
			ans.append(u)
			for i in adj[u]:
				in_degree[i] -= 1
				if in_degree[i] == 0:
					queue.append(i)
		return ans


class Solution:

	def topoSort(self, V, adj):

		def dfs(node, vis, adj, stack):
			vis[node] = 1
			for j in adj[node]:
				if not vis[j]:
					dfs(j, vis, adj, stack)
			stack.append(node)
		ans = []
		vis = [0] * V
		stack = []
		for i in range(V):
			if not vis[i]:
				dfs(i, vis, adj, stack)
		while stack:
			ans.append(stack.pop())
		return ans


class Solution:

	def dfs(self, node, adj, visited, stack):
		visited[node] = True
		for v in adj[node]:
			if not visited[v]:
				self.dfs(v, adj, visited, stack)
		stack.append(node)

	def topoSort(self, V, adj):
		visited = [False for i in range(0, V)]
		stack = []
		for i in range(0, V):
			if not visited[i]:
				self.dfs(i, adj, visited, stack)
		stack.reverse()
		return stack


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		indegree = [0] * V
		queue = deque()
		for i in range(V):
			for element in adj[i]:
				indegree[element] += 1
		for (index, element) in enumerate(indegree):
			if element == 0:
				queue.append(index)
		topoSort = []
		while queue:
			poppedNode = queue.popleft()
			topoSort.append(poppedNode)
			for neigh in adj[poppedNode]:
				indegree[neigh] -= 1
				if indegree[neigh] == 0:
					queue.append(neigh)
		return topoSort


class Solution:

	def dfs(self, currentNode, visited, adj, stack):
		visited[currentNode] = 1
		for neigh in adj[currentNode]:
			if visited[neigh] == 0:
				self.dfs(neigh, visited, adj, stack)
		stack.append(currentNode)
		return

	def topoSort(self, V, adj):
		visited = [0 for j in range(V)]
		stack = []
		for node in range(V):
			if visited[node] == 0:
				self.dfs(node, visited, adj, stack)
		return stack[::-1]


class Solution:

	def dfs(self, node, vis, adj, ans):
		vis.add(node)
		for nei in adj[node]:
			if nei not in vis:
				self.dfs(nei, vis, adj, ans)
		ans.append(node)

	def topoSort(self, V, adj):
		vis = set()
		ans = []
		for i in range(V):
			if i not in vis:
				self.dfs(i, vis, adj, ans)
		return ans[::-1]


class Solution:

	def topoSort(self, V, adj):
		inDegree = [0] * V
		for i in range(V):
			for n in adj[i]:
				inDegree[n] += 1
		queue = []
		for i in range(V):
			if inDegree[i] == 0:
				queue.append(i)
		topo = []
		while len(queue):
			node = queue.pop(0)
			topo.append(node)
			for ne in adj[node]:
				inDegree[ne] -= 1
				if inDegree[ne] == 0:
					queue.append(ne)
		return topo


from queue import Queue

class Solution:

	def dfs(self, node, adj, vis, st):
		vis[node] = 1
		for adjNode in adj[node]:
			if not vis[adjNode]:
				Solution.dfs(self, adjNode, adj, vis, st)
		st.append(node)

	def topoSort(self, V, adj):
		indegree = [0] * V
		for node in range(V):
			for adjNode in adj[node]:
				indegree[adjNode] += 1
		q = Queue()
		for node in range(V):
			if indegree[node] == 0:
				q.put(node)
		topo = []
		while not q.empty():
			node = q.get()
			topo.append(node)
			for adjNode in adj[node]:
				indegree[adjNode] -= 1
				if indegree[adjNode] == 0:
					q.put(adjNode)
		return topo


class Solution:

	def dfs(self, node, adj, vis, st):
		vis[node] = 1
		for adjNode in adj[node]:
			if not vis[adjNode]:
				Solution.dfs(self, adjNode, adj, vis, st)
		st.append(node)

	def topoSort(self, V, adj):
		vis = [0] * V
		st = []
		for i in range(V):
			if not vis[i]:
				Solution.dfs(self, i, adj, vis, st)
		return st[::-1]


class Solution:

	def topoSort(self, V, adj):
		stack = []
		visited = set()

		def dfs(u):
			if u in visited:
				return
			visited.add(u)
			for v in adj[u]:
				dfs(v)
			stack.append(u)
		for i in range(V):
			if i not in visited:
				dfs(i)
		stack.reverse()
		return stack


class Solution:

	def topoSort(self, V, adj):
		visited_set = set()
		topo_sort = []

		def dfs(node):
			visited_set.add(node)
			for neigh in adj[node]:
				if neigh not in visited_set:
					dfs(neigh)
			topo_sort.append(node)
			return
		for i in range(0, V):
			if i not in visited_set:
				dfs(i)
		topo_sort.reverse()
		return topo_sort


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		(topo, indegrees) = ([], [0] * V)
		for adjNodes in adj:
			for adjNode in adjNodes:
				indegrees[adjNode] += 1
		que = deque()
		for node in range(V):
			if indegrees[node] == 0:
				que.append(node)
		while que:
			node = que.popleft()
			topo.append(node)
			for adjNode in adj[node]:
				indegrees[adjNode] -= 1
				if indegrees[adjNode] == 0:
					que.append(adjNode)
		return topo


from collections import deque

class Solution:

	def dfs(self, node, adj, visited, topo):
		visited[node] = True
		for adjNode in adj[node]:
			if not visited[adjNode]:
				self.dfs(adjNode, adj, visited, topo)
		topo.append(node)

	def topoSort(self, V, adj):
		(topo, visited) = ([], [False] * V)
		for node in range(V):
			if not visited[node]:
				self.dfs(node, adj, visited, topo)
		topo.reverse()
		return topo


class Solution:

	def topoSort(self, V, adj):
		indeg = [0 for i in range(V)]
		for ele in adj:
			for each in ele:
				indeg[each] += 1
		q = []
		for i in range(V):
			if indeg[i] == 0:
				q.append(i)
		res = []
		while len(q) != 0:
			node = q.pop(0)
			res.append(node)
			for nbr in adj[node]:
				indeg[nbr] -= 1
				if indeg[nbr] == 0:
					q.append(nbr)
		return res


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		visit = [0] * V
		q = deque()
		for i in range(V):
			for j in adj[i]:
				visit[j] += 1
		for i in range(V):
			if visit[i] == 0:
				q.append(i)
		result = []
		while len(q):
			p = q.popleft()
			result.append(p)
			for i in adj[p]:
				visit[i] -= 1
				if visit[i] == 0:
					q.append(i)
		return result


class Solution:

	def topoSort(self, V, adj):

		def dfs(adj, visit, k, stack):
			visit[k] = 1
			for i in adj[k]:
				if not visit[i]:
					dfs(adj, visit, i, stack)
			stack.append(k)
		visit = [0] * V
		stack = []
		for i in range(V):
			if visit[i] == 0:
				dfs(adj, visit, i, stack)
		result = []
		while stack:
			result.append(stack.pop())
		return result


from collections import deque

class Solution:

	def topoSort(self, V, adj):
		inV = [0 for _ in range(V)]
		for i in range(len(adj)):
			for v in adj[i]:
				inV[v] += 1
		queue = deque()
		for i in range(V):
			if inV[i] == 0:
				queue.append(i)
		topo = []
		while queue:
			element = queue.popleft()
			topo.append(element)
			for v in adj[element]:
				if inV[v] == 1:
					inV[v] -= 1
					queue.append(v)
				else:
					inV[v] -= 1
		for i in range(V):
			if inV[i] != 0:
				return []
		return topo


from collections import *

class Solution:

	def topoSort(self, V, adj):

		def dfs(s, visited, stack, adj):
			visited[s] = True
			for x in adj[s]:
				if not visited[x]:
					dfs(x, visited, stack, adj)
			stack.append(s)
		visited = [False] * V
		stack = []
		for i in range(V):
			if not visited[i]:
				dfs(i, visited, stack, adj)
		ans = []
		while len(stack) != 0:
			x = stack.pop()
			ans.append(x)
		return ans


class Solution:

	def topoSort(self, V, adj):
		top_order = []
		nodes_processed = 0
		zero_in_v = []
		indeg = [0] * V
		for u in range(V):
			for v in adj[u]:
				indeg[v] += 1
		for u in range(V):
			if indeg[u] == 0:
				zero_in_v.append(u)
		while len(zero_in_v) > 0:
			zero_v = zero_in_v.pop()
			nodes_processed += 1
			top_order.append(zero_v)
			for v in adj[zero_v]:
				indeg[v] -= 1
				if indeg[v] == 0:
					zero_in_v.append(v)
		if nodes_processed != V:
			return -1
		return top_order


class Solution:

	def topoSort(self, V, adj):
		degree = [0] * V
		for i in range(len(adj)):
			for j in adj[i]:
				degree[j] += 1
		ans = []
		q = []
		for i in range(V):
			if degree[i] == 0:
				q.append(i)
		while q:
			node = q.pop(0)
			ans.append(node)
			for i in adj[node]:
				degree[i] -= 1
				if degree[i] == 0:
					q.append(i)
		return ans


class Solution:

	def solve(self, node, adj, st, vis):
		vis[node] = 1
		for i in adj[node]:
			if vis[i] != 1:
				self.solve(i, adj, st, vis)
		st.append(node)

	def topoSort(self, V, adj):
		st = []
		vis = [0] * (V + 1)
		for i in range(V):
			if vis[i] != 1:
				self.solve(i, adj, st, vis)
		ans = []
		while st:
			k = st.pop(-1)
			ans.append(k)
		return ans


class Solution:

	def topoSort(self, V, adj):
		visited = set()
		stack = []

		def topo(n):
			visited.add(n)
			for i in adj[n]:
				if i not in visited:
					topo(i)
			stack.append(n)
		for i in range(V):
			if i not in visited:
				topo(i)
		return stack[::-1]


import collections

class Solution:

	def topoSort(self, V, adj):
		incEdge = [0] * V
		for u in range(V):
			for v in adj[u]:
				incEdge[v] += 1
		q = collections.deque([])
		for (u, inc) in enumerate(incEdge):
			if inc == 0:
				q.append(u)
		ans = []
		while q:
			curr = q.popleft()
			ans.append(curr)
			for v in adj[curr]:
				incEdge[v] -= 1
				if incEdge[v] == 0:
					q.append(v)
		return ans


class Solution:

	def topoSort(self, V, adj):

		def dfs(u, stack):
			if vis[u]:
				return
			vis[u] = True
			for v in adj[u]:
				if not vis[v]:
					dfs(v, stack)
			stack.append(u)
		stack = []
		vis = [False] * V
		for i in range(V):
			if not vis[i]:
				dfs(i, stack)
		stack.reverse()
		return stack


class Solution:

	def topoSort(self, V, adj):

		def dfs(u, stack):
			if vis[u]:
				return
			vis[u] = True
			for v in adj[u]:
				if not vis[v]:
					dfs(v, stack)
			stack.append(u)
		stack = []
		vis = [False] * V
		for i in range(V):
			if not vis[i]:
				dfs(i, stack)
		ans = []
		while stack:
			ans.append(stack.pop())
		return ans