A directed graph of V vertices and E edges is given in the form of an adjacency list adj. Each node of the graph is labelled with a distinct integer in the range 0 to V - 1.
A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node.
You have to return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.
Example 1:
Input:
Output:
2 4 5 6
Explanation:
The given graph is shown above.
Nodes 5 and 6 are terminal nodes as there are no 
outgoing edges from either of them. 
Every path starting at nodes 2, 4, 5, and 6 all 
lead to either node 5 or 6.
Example 2:
Input:
Output:
3
Explanation:
Only node 3 is a terminal node, and every path 
starting at node 3 leads to node 3.
Your Task:
You don't need to read or print anything. Your task is to complete the function eventualSafeNodes() which takes an integer V denoting no. of vertices and adj denoting adjacency list of the graph and returns an array of safe nodes.
Expected Time Complexity: O(V + E)
Expected Space Complexity: O(V)
Constraints:
	1 <= V <= 10^{4}
	0 <= E <= 10^{4}
	The graph won't contain self loops.
	Each node in the graph has a distinct value in the range 0 to V - 1.

Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

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

Starter code:
#User function Template for python3



from typing import List



class Solution:    

    def eventualSafeNodes(self, V : int, adj : List[List[int]]) -> List[int]:

        # code here



Solutions:
from typing import List

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		adjrev = [[] for i in range(V)]
		indeg = [0] * V
		for i in range(V):
			for it in adj[i]:
				adjrev[it].append(i)
				indeg[i] += 1
		q = []
		for i in range(V):
			if indeg[i] == 0:
				q.append(i)
		safenodes = []
		while q:
			node = q.pop(0)
			safenodes.append(node)
			for it in adjrev[node]:
				indeg[it] -= 1
				if indeg[it] == 0:
					q.append(it)
		safenodes.sort()
		return safenodes


from typing import List

class Solution:

	def eventualSafeNodes(self, V, adj):
		revAdj = {}
		for i in range(V):
			revAdj[i] = []
		indegree = [0] * V
		for i in range(V):
			for adjacent in adj[i]:
				revAdj[adjacent].append(i)
				indegree[i] += 1
		q = []
		for i in range(len(indegree)):
			if indegree[i] == 0:
				q.append(i)
		ans = []
		while len(q) != 0:
			latest = q.pop(0)
			ans.append(latest)
			for i in range(len(revAdj[latest])):
				a = revAdj[latest].pop(0)
				indegree[a] -= 1
				if indegree[a] == 0:
					q.append(a)
		ans.sort()
		return ans


from typing import List
from collections import deque

class Solution:

	def eventualSafeNodes(self, V, adj):
		adjRev = [[] for _ in range(V)]
		indegree = [0] * V
		for i in range(V):
			for it in adj[i]:
				adjRev[it].append(i)
				indegree[i] += 1
		q = deque()
		safeNodes = []
		for i in range(V):
			if indegree[i] == 0:
				q.append(i)
		while q:
			node = q.popleft()
			safeNodes.append(node)
			for it in adjRev[node]:
				indegree[it] -= 1
				if indegree[it] == 0:
					q.append(it)
		safeNodes.sort()
		return safeNodes


import queue
from typing import List

class Solution:

	def eventualSafeNodes(self, v: int, adjList: List[List[int]]) -> List[int]:
		s = queue.Queue()
		adjRev = {}
		indegree = []
		res = []
		for i in range(v):
			adjRev[i] = []
			indegree.append(0)
		for i in range(v):
			for j in adjList[i]:
				adjRev[j].append(i)
				indegree[i] += 1
		for i in range(v):
			if indegree[i] == 0:
				s.put(i)
		while not s.empty():
			cur = s.get()
			res.append(cur)
			for i in adjRev[cur]:
				indegree[i] -= 1
				if indegree[i] == 0:
					s.put(i)
		return sorted(res)


from typing import List

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		indegree = [0] * V
		queue = []
		adj_rev = [[] for i in range(V)]
		ans = []
		for i in range(V):
			for j in adj[i]:
				adj_rev[j].append(i)
				indegree[i] += 1
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
		while queue:
			x = queue.pop()
			ans.append(x)
			for i in adj_rev[x]:
				indegree[i] -= 1
				if indegree[i] == 0:
					queue.append(i)
		ans.sort()
		return ans


from typing import List
from typing import List

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		newAdj = [[] for i in range(V)]
		ind = [0] * V
		for i in range(V):
			for j in adj[i]:
				newAdj[j].append(i)
				ind[i] += 1
		queue = []
		for i in range(V):
			if ind[i] == 0:
				queue.append(i)
		ans = []
		while queue:
			a = queue.pop(0)
			ans.append(a)
			for i in newAdj[a]:
				ind[i] -= 1
				if ind[i] == 0:
					queue.append(i)
		return sorted(ans)


from typing import List
from queue import deque

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		indegree = {}
		q = deque()
		adj1 = [[] for j in range(V)]
		for i in range(len(adj)):
			for j in adj[i]:
				adj1[j].append(i)
		for i in range(V):
			indegree[i] = 0
		for i in adj1:
			for j in i:
				indegree[j] = indegree[j] + 1
		for i in indegree:
			if indegree[i] == 0:
				q.append(i)
		ans = []
		while q:
			node = q.popleft()
			ans.append(node)
			for i in adj1[node]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.append(i)
		return sorted(ans)

class Solution1:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:

		def dfs(node):
			visited[node] = True
			path_visited[node] = True
			for i in adj[node]:
				if not visited[i]:
					if dfs(i) == True:
						return True
				elif path_visited[i]:
					return True
			check[node] = True
			path_visited[node] = False
			return False
		visited = [False] * V
		path_visited = [False] * V
		check = [False] * V
		safeNodes = []
		for i in range(V):
			if visited[i] == False:
				dfs(i)
		for j in range(V):
			if check[j] == 1:
				safeNodes.append(j)
		return safeNodes


from typing import List
from collections import deque

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		outV = [0 for _ in range(V)]
		revGraph = [[] for _ in range(V)]
		for i in range(V):
			outV[i] += len(adj[i])
			for v in adj[i]:
				revGraph[v].append(i)
		queue = deque()
		for i in range(V):
			if outV[i] == 0:
				queue.append(i)
		answer = []
		while queue:
			e = queue.popleft()
			answer.append(e)
			for v in revGraph[e]:
				if outV[v] == 1:
					outV[v] -= 1
					queue.append(v)
				else:
					outV[v] -= 1
		return sorted(answer)


from collections import deque
from typing import List

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		adj_rev = [[] for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				adj_rev[j].append(i)
		indegree = {}
		for i in range(V):
			indegree[i] = 0
		for i in range(V):
			for j in adj_rev[i]:
				if j in indegree:
					indegree[j] += 1
		que = deque()
		ans = []
		for (i, j) in indegree.items():
			if j == 0:
				que.append(i)
		while que:
			node = que.popleft()
			ans.append(node)
			for nbr in adj_rev[node]:
				indegree[nbr] -= 1
				if indegree[nbr] == 0:
					que.append(nbr)
		ans.sort()
		return ans


from typing import List
import sys
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict as dq

class Solution:

	def eventualSafeNodes(self, n: int, grid: List[List[int]]) -> List[int]:
		ind = [0] * n
		ans = [0] * n
		q = []
		d = dq(list)
		ptr = 0
		for i in range(n):
			for j in grid[i]:
				d[j].append(i)
				ind[i] += 1
		for i in range(n):
			if ind[i] == 0:
				q.append(i)
		while ptr < len(q):
			for j in d[q[ptr]]:
				ind[j] -= 1
				if ind[j] == 0:
					q.append(j)
			ans[q[ptr]] = 1
			ptr += 1
		q = []
		for j in range(n):
			if ans[j] == 1:
				q.append(j)
		return q


from typing import List
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def rec(self, grid, visited, node):
		con = 1
		visited[node] = 1
		if len(grid[node]) == 0:
			visited[node] = 'x'
			return 'x'
		for i in grid[node]:
			if visited[i] == 0:
				visited[i] = 1
				ans = self.rec(grid, visited, i)
				if ans != 'x':
					con = 0
			elif visited[i] == 1:
				con = 0
		if con:
			visited[node] = 'x'
			return 'x'
		return 1

	def eventualSafeNodes(self, n: int, grid: List[List[int]]) -> List[int]:
		visited = [0] * n
		for i in range(n):
			if visited[i] == 0:
				visited[i] = self.rec(grid, visited, i)
		ans = []
		for j in range(n):
			if visited[j] == 'x':
				ans.append(j)
		return ans


from queue import deque
from typing import List

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		adjRev = [[] for _ in range(V)]
		for i in range(V):
			for j in adj[i]:
				adjRev[j].append(i)
		indegree = {}
		for i in range(V):
			indegree[i] = 0
		for i in adjRev:
			for j in i:
				indegree[j] += 1
		q = deque()
		for i in indegree:
			if indegree[i] == 0:
				q.append(i)
		ans = []
		while q:
			node = q.popleft()
			ans.append(node)
			for nbr in adjRev[node]:
				indegree[nbr] -= 1
				if indegree[nbr] == 0:
					q.append(nbr)
		ans.sort()
		return ans


from typing import List
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, node, vis, pathvis, graph, check):
		vis[node] = 1
		pathvis[node] = 1
		check[node] = 0
		for i in graph[node]:
			if vis[i] == -1:
				if self.dfs(i, vis, pathvis, graph, check) == True:
					return True
			elif pathvis[i]:
				return True
		check[node] = 1
		pathvis[node] = 0
		return False

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		vis = [-1] * V
		pathvis = [-1] * V
		(safe, check) = ([], [0] * V)
		for i in range(V):
			if vis[i] == -1:
				self.dfs(i, vis, pathvis, adj, check)
		for i in range(V):
			if check[i] == 1:
				safe.append(i)
		return safe


from collections import deque
from typing import List

class Solution:

	def eventualSafeNodes(self, n: int, graph: List[List[int]]) -> List[int]:
		revAdj = [[] for _ in range(n)]
		for i in range(n):
			for it in graph[i]:
				revAdj[it].append(i)
		inDegree = [0] * n
		for i in range(n):
			for it in revAdj[i]:
				inDegree[it] += 1
		q = deque()
		for i in range(n):
			if inDegree[i] == 0:
				q.append(i)
		ans = []
		while q:
			node = q.popleft()
			ans.append(node)
			for it in revAdj[node]:
				inDegree[it] -= 1
				if inDegree[it] == 0:
					q.append(it)
		ans.sort()
		return ans


from typing import List
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

class Solution:

	def dfsCheck(self, node, adj, vis, pathVis, check):
		vis[node] = 1
		pathVis[node] = 1
		check[node] = 0
		for it in adj[node]:
			if vis[it] == 0:
				if self.dfsCheck(it, adj, vis, pathVis, check):
					return True
			elif vis[it] == 1 and pathVis[it] == 1:
				return True
		check[node] = 1
		pathVis[node] = 0
		return False

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		vis = [0] * V
		pathVis = [0] * V
		check = [0] * V
		ans = []
		for i in range(V):
			if vis[i] == 0:
				self.dfsCheck(i, adj, vis, pathVis, check)
		for i in range(V):
			if check[i] == 1:
				ans.append(i)
		return ans


from typing import List
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		visit = [0] * V
		dvisit = [0] * V
		ans = []

		def dfs(i):
			visit[i] = 1
			dvisit[i] = 1
			for j in adj[i]:
				if visit[j] == 0:
					if dfs(j):
						return True
				elif dvisit[j] == 1:
					return True
			dvisit[i] = 0
			return False
		for i in range(V):
			if visit[i] == 0:
				dfs(i)
		for i in range(V):
			if dvisit[i] == 0:
				ans.append(i)
		return ans


from typing import List
import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def __detect__(self, adjacency_list: List[List[int]], visited_array: List[bool], root: int, tracker_arr: List[int]) -> bool:
		visited_array[root] = True
		tracker_arr[root] = True
		for ele in adjacency_list[root]:
			if not visited_array[ele]:
				has_cycle = self.__detect__(adjacency_list, visited_array, ele, tracker_arr)
				if has_cycle:
					return True
			elif tracker_arr[ele]:
				return True
		tracker_arr[root] = False
		return False

	def eventualSafeNodes(self, vertices: int, adjacency_list: List[List[int]]) -> List[int]:
		visited_array = [False for _ in range(vertices)]
		tracker_arr = [False for _ in range(vertices)]
		for root in range(vertices):
			if not visited_array[root]:
				self.__detect__(adjacency_list, visited_array, root, tracker_arr)
		return [i for i in range(len(tracker_arr)) if not tracker_arr[i]]


from typing import List

class Solution1:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		path_vis = [0] * V
		vis = [0] * V
		check = [0] * V

		def dfs(node, vis, path_vis):
			vis[node] = 1
			path_vis[node] = 1
			for i in adj[node]:
				if vis[i] == 0:
					if dfs(i, vis, path_vis):
						return 1
				elif path_vis[i] == 1:
					return 1
			check[node] = 1
			path_vis[node] = 0
			return 0
		for i in range(V):
			if vis[i] == 0:
				dfs(i, vis, path_vis)
		ans = []
		for i in range(V):
			if check[i]:
				ans.append(i)
		return ans

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		new_adj = [[] for _ in range(V)]
		indegree = [0] * V
		for i in range(V):
			for j in adj[i]:
				new_adj[j].append(i)
				indegree[i] += 1
		ans = []
		queue = []
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
				ans.append(i)
		while queue:
			x = queue.pop(0)
			for j in new_adj[x]:
				indegree[j] -= 1
				if indegree[j] == 0:
					queue.append(j)
					ans.append(j)
		ans.sort()
		return ans


from typing import List

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		adjrev = []
		indegree = []
		for i in range(V):
			adjrev.append([])
			indegree.append(0)
		for i in range(V):
			for j in adj[i]:
				adjrev[j].append(i)
				indegree[i] += 1
		q = []
		for i in range(V):
			if indegree[i] == 0:
				q.append(i)
		arr = []
		while len(q) != 0:
			for i in adjrev[q[0]]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.append(i)
			arr.append(q[0])
			q.pop(0)
		arr.sort()
		return arr


from typing import List
from collections import deque

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		ans = []
		m = [[set(), [i, 0]] for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				m[j][0].add(i)
				m[i][1][1] += 1
		q = deque()
		for el in m:
			if el[1][1] == 0:
				q.appendleft(el)
		while q:
			p = q.pop()
			ans.append(p[1][0])
			for el in p[0]:
				m[el][1][1] -= 1
				if m[el][1][1] == 0:
					q.appendleft(m[el])
		ans.sort()
		return ans


from typing import List

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		V = len(adj)
		revadj = [[] for i in range(V)]
		for i in range(V):
			for ele in adj[i]:
				revadj[ele].append(i)
		indegree = [0] * V
		for lst in revadj:
			for i in lst:
				indegree[i] += 1
		stack = []
		result = []
		for i in range(V):
			if indegree[i] == 0:
				stack.append(i)
		while stack:
			s = stack.pop()
			result.append(s)
			for i in revadj[s]:
				indegree[i] -= 1
				if indegree[i] == 0:
					stack.append(i)
		return sorted(result)


from typing import List

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		adjRev = {i: [] for i in range(V)}
		indegree = [0 for i in range(V)]
		for i in range(V):
			for node in adj[i]:
				adjRev[node].append(i)
				indegree[i] += 1
		queue = []
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
		safeNodes = []
		while len(queue):
			node = queue.pop(-1)
			safeNodes.append(node)
			for i in adjRev[node]:
				indegree[i] -= 1
				if indegree[i] == 0:
					queue.append(i)
		return sorted(safeNodes)


from typing import List
import sys
sys.setrecursionlimit(1000000)

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		an = [0] * V
		vis = [0] * V

		def dfs(node):
			nonlocal an, vis
			vis[node] = 1
			for i in adj[node]:
				if vis[i] == 1:
					an[node] = 1
				else:
					x = dfs(i)
					an[node] |= x
			vis[node] = 2
			return an[node]
		for i in range(V):
			if vis[i] == 0:
				dfs(i)
		temp = []
		for i in range(V):
			if an[i] == 0:
				temp.append(i)
		return temp


from typing import List
from collections import deque

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		rev = [[] for i in range(V)]
		ind = [0] * V
		for i in range(V):
			for j in adj[i]:
				rev[j].append(i)
				ind[i] += 1
		ans = []
		q = deque()
		for i in range(V):
			if ind[i] == 0:
				q.append(i)
		while q:
			node = q.popleft()
			ans.append(node)
			for i in rev[node]:
				ind[i] -= 1
				if ind[i] == 0:
					q.append(i)
		ans.sort()
		return ans


from typing import List
import sys
sys.setrecursionlimit(20000)

class Solution:

	def dfs(self, v, adj):
		self.marked[v] = 1
		for w in adj[v]:
			if self.marked[w] == 0:
				self.path[w] = v
				self.dfs(w, adj)
			elif self.marked[w] == 1:
				k = v
				while k != w:
					self.marked[k] = 3
					k = self.path[k]
				self.marked[w] = 3
			elif self.marked[w] == 3:
				k = v
				while k != -1 and self.marked[k] != 3:
					self.marked[k] = 3
					k = self.path[k]
		self.marked[v] = 2
		for w in adj[v]:
			if self.marked[w] == 3:
				self.marked[v] = 3
				break

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		self.marked = [0] * V
		self.path = [-1] * V
		for i in range(V):
			if self.marked[i] == 0:
				self.dfs(i, adj)
		return [i for i in range(V) if self.marked[i] == 2]


from typing import List

class Solution:

	def eventualSafeNodes(self, V: int, adjL: List[List[int]]) -> List[int]:
		indegree = [0 for i in range(V)]
		adj = [[] for i in range(V)]
		for i in range(V):
			for e in adjL[i]:
				adj[e].append(i)
		for elem in adj:
			for it in elem:
				indegree[it] += 1
		queue = []
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
		topo = []
		while len(queue) > 0:
			e = queue.pop(0)
			topo.append(e)
			for x in adj[e]:
				indegree[x] -= 1
				if indegree[x] == 0:
					queue.append(x)
		topo.sort()
		return topo


import sys
from typing import List
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, i, visited, path_visited, safe_nodes, adj):
		visited[i] = 1
		path_visited[i] = 1
		for neighbors in adj[i]:
			if visited[neighbors] == 0:
				if self.dfs(neighbors, visited, path_visited, safe_nodes, adj):
					return True
			elif visited[neighbors] == 1 and path_visited[neighbors] == 1:
				return True
		path_visited[i] = 0
		safe_nodes[i] = 1
		return False

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = [0 for i in range(V)]
		path_visited = [0 for i in range(V)]
		safe_nodes = [0 for i in range(V)]
		for i in range(V):
			if visited[i] == 0:
				self.dfs(i, visited, path_visited, safe_nodes, adj)
		final_ans = []
		for i in range(len(safe_nodes)):
			if safe_nodes[i] == 1:
				final_ans.append(i)
		return final_ans


from typing import List

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		adjrev = [[] for i in range(V)]
		indeg = [0 for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				adjrev[j].append(i)
				indeg[i] += 1
		safe = []
		q = []
		for i in range(V):
			if indeg[i] == 0:
				q.append(i)
		while q:
			x = q.pop(0)
			safe.append(x)
			for i in adjrev[x]:
				indeg[i] -= 1
				if indeg[i] == 0:
					q.append(i)
		safe.sort()
		return safe


from collections import deque
from typing import List

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		revadj = [[] for _ in range(V)]
		indegree = [0] * V
		for v in range(V):
			for item in adj[v]:
				revadj[item].append(v)
				indegree[v] += 1
		q = deque()
		res = []
		for v in range(V):
			if indegree[v] == 0:
				q.append(v)
		while q:
			node = q.popleft()
			res.append(node)
			for item in revadj[node]:
				indegree[item] -= 1
				if indegree[item] == 0:
					q.append(item)
		res.sort()
		return res


from typing import List
import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		g1 = dict()
		for i in range(V):
			g1[i] = True
		terminal = dict()
		for i in range(len(adj)):
			if len(adj[i]) == 0:
				terminal[i] = True
		l = []
		g3 = dict()

		def dfs(g1, g2, terminal, s):
			if terminal.get(s) != None:
				return True
			if g2[s] == False:
				if g3.get(s) == None:
					return False
				return g3[s]
			g2[s] = False
			y = True
			for i in g1[s]:
				y = y and dfs(g1, g2, terminal, i)
			if y:
				l.append(s)
			g3[s] = y
			return y
		for i in range(V):
			if g1[i]:
				dfs(adj, g1, terminal, i)
		for i in terminal:
			l.append(i)
		l.sort()
		return l


from typing import List
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

class Solution:

	def eventualSafeNodes(self, V: int, graph: List[List[int]]) -> List[int]:
		vis = [0 for _ in range(len(graph))]
		pathVis = [0 for _ in range(len(graph))]
		check = [True for _ in range(len(graph))]

		def dfs(i, vis, pathVis, graph, check):
			vis[i] = 1
			pathVis[i] = 1
			for node in graph[i]:
				if vis[node] == 0:
					if dfs(node, vis, pathVis, graph, check) == False:
						check[node] = False
						return False
				elif pathVis[node] == 1:
					check[node] = False
					return False
			pathVis[i] = 0
			return True
		ans = []
		for i in range(len(graph)):
			if vis[i] == 0:
				if dfs(i, vis, pathVis, graph, check) == False:
					check[i] = False
		for i in range(len(check)):
			if check[i] == True:
				ans.append(i)
		return ans


from typing import List
from collections import defaultdict, deque

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		graph = defaultdict(list)
		indegree = [0] * V
		for i in range(V):
			for j in adj[i]:
				graph[j].append(i)
				indegree[i] += 1
		queue = deque()
		result = []
		for i in range(len(indegree)):
			if indegree[i] == 0:
				queue.append(i)
		while queue:
			node = queue.popleft()
			result.append(node)
			for nei in graph[node]:
				indegree[nei] -= 1
				if indegree[nei] == 0:
					queue.append(nei)
		return sorted(result)


from collections import deque
from typing import List

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		indegree = [0] * V
		adj1 = [[] for _ in range(V)]
		for i in range(V):
			for it in adj[i]:
				adj1[it].append(i)
				indegree[i] += 1
		q = deque()
		for i in range(V):
			if indegree[i] == 0:
				q.append(i)
		topo = []
		while q:
			node = q.popleft()
			topo.append(node)
			for it in adj1[node]:
				indegree[it] -= 1
				if indegree[it] == 0:
					q.append(it)
		return sorted(topo)


from typing import List
import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def checkcycle(self, vertex, visited, dfsvis, adj, checkNode):
		visited[vertex] = True
		dfsvis[vertex] = True
		checkNode[vertex] = False
		for node in adj[vertex]:
			if visited[node] == False:
				if self.checkcycle(node, visited, dfsvis, adj, checkNode) == True:
					return True
			elif dfsvis[node] == True:
				return True
		dfsvis[vertex] = False
		checkNode[vertex] = True
		return False

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		visited = [False] * V
		dfsvis = [False] * V
		safeNode = []
		checkNode = [False] * V
		for i in range(V):
			if visited[i] == False:
				self.checkcycle(i, visited, dfsvis, adj, checkNode)
		for i in range(V):
			if checkNode[i] == True:
				safeNode.append(i)
		return safeNode


from typing import List
from collections import defaultdict, deque

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		graph = defaultdict(list)
		indegree = [0] * V
		for (v, edges) in enumerate(adj):
			for neigh in edges:
				graph[neigh].append(v)
				indegree[v] += 1
		queue = deque()
		for i in range(len(indegree)):
			if indegree[i] == 0:
				queue.append(i)
		ans = []
		while queue:
			node = queue.popleft()
			ans.append(node)
			for child in graph[node]:
				indegree[child] -= 1
				if indegree[child] == 0:
					queue.append(child)
		return sorted(ans)


from typing import List
import sys
sys.setrecursionlimit(10 ** 8)

def dfs(u, adj, is_visited, in_stack, nodes_present_in_cycle):
	is_visited[u] = True
	in_stack[u] = True
	for v in adj[u]:
		if not is_visited[v]:
			is_cycle_present = dfs(v, adj, is_visited, in_stack, nodes_present_in_cycle)
			if is_cycle_present:
				nodes_present_in_cycle[u] = True
				return True
		elif is_visited[v] and in_stack[v]:
			nodes_present_in_cycle[u] = True
			return True
	in_stack[u] = False
	return False

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		safeNodes = []
		is_visited = [False] * V
		in_stack = [False] * V
		nodes_present_in_cycle = [False] * V
		for i in range(V):
			if not is_visited[i]:
				dfs(i, adj, is_visited, in_stack, nodes_present_in_cycle)
		for i in range(V):
			if not nodes_present_in_cycle[i]:
				safeNodes.append(i)
		return safeNodes


from typing import List
from collections import defaultdict

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		adjrev = defaultdict(list)
		ind = [0] * V
		for i in range(V):
			for it in adj[i]:
				adjrev[it].append(i)
				ind[i] += 1
		q = []
		for i in range(V):
			if ind[i] == 0:
				q.append(i)
		safen = []
		while q:
			temp = q.pop(0)
			safen.append(temp)
			for i in adjrev[temp]:
				ind[i] -= 1
				if ind[i] == 0:
					q.append(i)
		safen.sort()
		return safen


from typing import List
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		graph = adj
		v = len(graph)
		vis = [0 for i in range(v + 1)]
		pathvis = [0 for i in range(v + 1)]
		check = [0 for i in range(v + 1)]
		safeStates = []
		for i in range(v):
			if vis[i] == 0:
				node = i
				self.dfsCheck(node, graph, vis, pathvis, check)
		for i in range(v):
			if check[i] == 1:
				safeStates.append(i)
		return safeStates

	def dfsCheck(self, node, mat, vis, pathvis, check):
		vis[node] = 1
		pathvis[node] = 1
		check[node] = 0
		for n in mat[node]:
			if pathvis[n] == 1 and vis[n] == 1:
				return True
			elif vis[n] == 0:
				if self.dfsCheck(n, mat, vis, pathvis, check) == True:
					return True
		check[node] = 1
		pathvis[node] = 0
		return False


from collections import defaultdict, deque
from typing import List
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		adjrev = defaultdict(list)
		indegree = [0] * V
		for i in range(V):
			for nodes in adj[i]:
				adjrev[nodes].append(i)
				indegree[i] += 1
		q = deque()
		for i in range(V):
			if indegree[i] == 0:
				q.append(i)
		ans = []
		while q:
			node = q.popleft()
			ans.append(node)
			for neighbor in adjrev[node]:
				indegree[neighbor] -= 1
				if indegree[neighbor] == 0:
					q.append(neighbor)
		return sorted(ans)


def dfs(i, adj, vis, pathvis, check):
	vis[i] = 1
	pathvis[i] = 1
	check[i] = 0
	for j in adj[i]:
		if vis[j] == 0:
			if dfs(j, adj, vis, pathvis, check) == True:
				return True
		elif pathvis[j] == 1:
			return True
	pathvis[i] = 0
	check[i] = 1
	return False
from typing import List
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def eventualSafeNodes(self, v: int, adj: List[List[int]]) -> List[int]:
		pathvis = [0] * v
		vis = [0] * v
		safe = [0] * v
		b = []
		for i in range(v):
			if vis[i] == 0:
				dfs(i, adj, vis, pathvis, safe)
		for i in range(v):
			if safe[i] == 1:
				b.append(i)
		return b


from typing import List
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:

		def _dfs(u):
			if u in vis:
				states[u] = UNSAFE
				return False
			vis.add(u)
			for v in adj[u]:
				if not _dfs(v) or states[v] == UNSAFE:
					states[u] = UNSAFE
					return False
			vis.remove(u)
			states[u] = SAFE
			return True
		(UNKNOWN, SAFE, UNSAFE) = (0, 1, 2)
		vis = set()
		states = [UNKNOWN] * V
		for i in range(V):
			if states[i] != UNKNOWN:
				continue
			_dfs(i)
		return [i for (i, v) in enumerate(states) if v == SAFE]


from typing import List
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		vis = [0 for _ in range(V)]
		path = vis[:]
		check = vis[:]
		safe = []

		def dfs(root):
			vis[root] = 1
			path[root] = 1
			for node in adj[root]:
				if not vis[node]:
					if dfs(node):
						return True
				elif path[node]:
					return True
			check[root] = 1
			path[root] = 0
			return False
		for i in range(V):
			if not vis[i]:
				dfs(i)
		for i in range(V):
			if check[i]:
				safe.append(i)
		return safe


from typing import List

class Solution:

	def eventualSafeNodes(self, v: int, graph: List[List[int]]) -> List[int]:
		revgraph = []
		for i in range(v):
			revgraph.append([])
		deg = [0] * v
		for i in range(v):
			for node in graph[i]:
				revgraph[node].append(i)
				deg[i] += 1
		from collections import deque
		queue = deque()
		for i in range(v):
			if deg[i] == 0:
				queue.append(i)
		visited = [0] * v
		ans = []
		while queue:
			node = queue.popleft()
			visited[node] = 1
			for adnode in revgraph[node]:
				deg[adnode] -= 1
				if deg[adnode] == 0:
					queue.append(adnode)
		for i in range(v):
			if visited[i]:
				ans.append(i)
		return ans


from typing import List
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, start, adj, vis, pathvis, check):
		vis[start] = 1
		pathvis[start] = 1
		check[start] = 0
		for node in adj[start]:
			if vis[node] == 0:
				if self.dfs(node, adj, vis, pathvis, check) == True:
					check[node] = 0
					return True
			elif pathvis[node] == 1:
				check[node] = 0
				return True
		check[start] = 1
		pathvis[start] = 0
		return False

	def eventualSafeNodes(self, n: int, adj: List[List[int]]) -> List[int]:
		vis = [0] * n
		pathvis = [0] * n
		check = [0] * n
		ans = []
		for i in range(n):
			if not vis[i]:
				self.dfs(i, adj, vis, pathvis, check)
		for i in range(n):
			if check[i]:
				ans.append(i)
		return ans


from collections import *
from typing import List
import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def eventualSafeNodes(self, N: int, adj: List[List[int]]) -> List[int]:
		graph = defaultdict(list)
		for node in range(N):
			for nei in adj[node]:
				graph[nei].append(node)
		indeg = [0] * N
		for i in range(N):
			for node in graph[i]:
				indeg[node] += 1
		qu = deque()
		for i in range(N):
			if indeg[i] == 0:
				qu.append(i)
		ans = []
		while qu:
			curr = qu.popleft()
			ans.append(curr)
			for nei in graph[curr]:
				indeg[nei] -= 1
				if indeg[nei] == 0:
					qu.append(nei)
		return sorted(ans)


from queue import Queue
from typing import List

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		q = Queue()
		ans = []
		adjrev = [[] for i in range(V)]
		for i in range(V):
			for x in adj[i]:
				adjrev[x].append(i)
		ind = [0 for i in range(V)]
		for i in range(V):
			for x in adjrev[i]:
				ind[x] += 1
		for i in range(V):
			if ind[i] == 0:
				q.put(i)
		while q.qsize() != 0:
			node = q.get()
			ans.append(node)
			for x in adjrev[node]:
				ind[x] -= 1
				if ind[x] == 0:
					q.put(x)
		ans.sort()
		return ans


from typing import List
import sys
sys.setrecursionlimit(10 ** 9)

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:

		def dfs(node):
			visited.add(node)
			seen.add(node)
			for nei in adj[node]:
				if nei not in visited:
					if dfs(nei):
						return True
				elif nei in seen:
					return True
			seen.remove(node)
			ans.append(node)
			return False
		visited = set()
		seen = set()
		ans = []
		for i in range(V):
			if i not in visited:
				dfs(i)
		return sorted(ans)


from collections import defaultdict
from typing import List

class Solution:

	def eventualSafeNodes(self, V: int, graph: List[List[int]]) -> List[int]:
		g = defaultdict(list)
		res = []
		indeg = defaultdict(int)
		for i in range(len(graph)):
			for j in graph[i]:
				g[j].append(i)
		for src in g:
			for nei in g[src]:
				indeg[nei] += 1
		stack = [node for node in range(len(graph)) if indeg[node] == 0]
		while stack:
			node = stack.pop()
			res.append(node)
			for nei in g[node]:
				indeg[nei] -= 1
				if indeg[nei] == 0:
					stack.append(nei)
		res.sort()
		return res


from typing import List
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		(vis, pathvis) = (set(), set())

		def dfs(i):
			vis.add(i)
			pathvis.add(i)
			for adjNode in adj[i]:
				if adjNode not in vis:
					if dfs(adjNode):
						return True
				elif adjNode in pathvis:
					return True
			pathvis.remove(i)
			return False
		for i in range(V):
			if i not in vis:
				dfs(i)
		ans = []
		for i in range(V):
			if i not in pathvis:
				ans.append(i)
		return sorted(ans)


from typing import List
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:

		def dfs(src):
			visited[src] = 1
			pathVisited[src] = 1
			check[src] = 0
			for i in range(len(adj[src])):
				if visited[adj[src][i]] != 1:
					if dfs(adj[src][i]) == True:
						return True
				elif pathVisited[adj[src][i]] == 1:
					return True
			check[src] = 1
			pathVisited[src] = 0
			return False
		visited = [0] * V
		pathVisited = [0] * V
		check = [0] * V
		safeNode = []
		for i in range(V):
			if visited[i] != 1:
				dfs(i)
		for i in range(len(check)):
			if check[i] == 1:
				safeNode.append(i)
		return safeNode


from collections import deque
from typing import List

class Solution:

	def eventualSafeNodes(self, V: int, adj: List[List[int]]) -> List[int]:
		graph = [[] for _ in range(V)]
		indegree = [0] * V
		for v in range(V):
			for u in adj[v]:
				graph[u].append(v)
				indegree[v] += 1
		queue = deque()
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
		ans = []
		while queue:
			node = queue.popleft()
			ans.append(node)
			for nei in graph[node]:
				indegree[nei] -= 1
				if indegree[nei] == 0:
					queue.append(nei)
		return sorted(ans)