In a directed graph, we start at some node and every turn, walk along a directed edge of the graph.  If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.
Now, say our starting node is eventually safe if and only if we must eventually walk to a terminal node.  More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps.
Which nodes are eventually safe?  Return them as an array in sorted order.
The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the length of graph.  The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph.
Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Here is a diagram of the above graph.



Note:

graph will have length at most 10000.
The number of edges in the graph will not exceed 32000.
Each graph[i] will be a sorted list of different integers, chosen within the range [0, graph.length - 1].

Source: leetcode | Difficulty: MEDIUM
Tags: Graph algorithms

Graph traversal

Directed graphs

Starter code: class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        

Solutions:
class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		N = len(graph)
		if N == 0:
			return []
		color = [0] * N
		in_cycle = set()

		def dfs(i):
			if color[i] != 0:
				return color[i] == 2
			color[i] = 1
			for j in graph[i]:
				if color[j] == 2:
					continue
				elif color[j] == 1 or dfs(j) == False:
					return False
			color[i] = 2
			return True
		ret = []
		for i in range(N):
			if dfs(i):
				ret.append(i)
		return ret


class Solution:

	def dfs(self, node, v, g):
		if v[node] == 2:
			return False
		if v[node] == 1:
			return True
		if len(g[node]) == 0:
			v[node] = 2
			return False
		v[node] = 1
		for i in g[node]:
			if self.dfs(i, v, g):
				return True
		v[node] = 2
		return False

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		if len(graph) == 0:
			return []
		g = {}
		v = [0] * len(graph)
		ans = set()
		for i in range(len(graph)):
			if not self.dfs(i, v, graph):
				ans.add(i)
		ans = list(ans)
		ans.sort()
		return ans


from collections import defaultdict

class Solution:

	def eventualSafeNodes(self, graph):
		state = defaultdict(lambda : 'unknown')

		def dfs(node):
			if state[node] != 'unknown':
				return state[node] == 'safe'
			state[node] = 'visiting'
			for nei in graph[node]:
				if state[nei] == 'visiting' or not dfs(nei):
					return False
			state[node] = 'safe'
			return True
		N = len(graph)
		return [node for node in range(N) if dfs(node)]


import collections

class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		Terminal = []
		dict_raw = dict()
		dict_idx = collections.defaultdict(list)
		for (i, ele) in enumerate(graph):
			dict_raw[i] = set(ele)
			if ele == []:
				Terminal.append(i)
			else:
				for idx in ele:
					dict_idx[idx].append(i)
		stack = Terminal
		safe = set(Terminal)
		while stack:
			node = stack.pop()
			for ele_1 in dict_idx[node]:
				if dict_raw[ele_1].issubset(safe) and ele_1 not in safe:
					safe.add(ele_1)
					stack.append(ele_1)
		res = list(safe)
		return sorted(res)


class Solution:

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

		def cycle(snode):
			if mem[snode] == -1:
				return True
			elif mem[snode] == 1:
				return False
			mem[snode] = -1
			for e in graph[snode]:
				res = cycle(e)
				if res:
					return True
			mem[snode] = 1
			return False
		n = len(graph)
		ret = []
		mem = [0] * n
		for i in range(n):
			if not cycle(i):
				ret.append(i)
		return ret


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		if not graph:
			return None
		n = len(graph)
		(out_degree, rgraph) = (collections.Counter(), collections.defaultdict(set))
		for (node, neighbors) in enumerate(graph):
			for nei in neighbors:
				out_degree[node] += 1
				rgraph[nei].add(node)
		q = collections.deque([x for x in range(n) if out_degree[x] == 0])
		ans = []
		while q:
			node = q.popleft()
			ans.append(node)
			for nei in rgraph[node]:
				if out_degree[nei] == 0:
					continue
				out_degree[nei] -= 1
				if out_degree[nei] == 0:
					q.append(nei)
		ans.sort()
		return ans


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		if not graph:
			return []
		n = len(graph)
		adj = collections.defaultdict(set)
		for i in range(n):
			for j in graph[i]:
				adj[j].add(i)
		res = [i for i in range(n) if not graph[i]]
		outdegree = [len(graph[i]) for i in range(n)]
		Q = collections.deque(res)
		while Q:
			cur = Q.popleft()
			for i in adj[cur]:
				outdegree[i] -= 1
				if outdegree[i] == 0:
					res.append(i)
					Q.append(i)
		return sorted(res)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		state = [-1] * n

		def dfs(node):
			state[node] = 0
			for adj in graph[node]:
				if state[adj] == 0 or (state[adj] == -1 and dfs(adj)):
					return True
			state[node] = 1
		for i in range(n):
			if state[i] == -1:
				dfs(i)
		return [i for i in range(n) if state[i] == 1]


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		outdegree = collections.defaultdict(int)
		dic = collections.defaultdict(list)
		queue = collections.deque()
		(visited, res) = (set(), [])
		for i in range(len(graph)):
			outdegree[i] += len(graph[i])
			if not graph[i]:
				queue.append(i)
				visited.add(i)
			for node in graph[i]:
				dic[node].append(i)
		while queue:
			node = queue.popleft()
			res.append(node)
			for nbr in dic[node]:
				outdegree[nbr] -= 1
				if nbr not in visited and outdegree[nbr] == 0:
					queue.append(nbr)
					visited.add(nbr)
		return sorted(res)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		N = len(graph)
		re = [set() for _ in range(N)]
		q = collections.deque([])
		for (i, v) in enumerate(graph):
			if not v:
				q.append(i)
			for j in v:
				re[j].add(i)
		res = []
		while q:
			temp = q.popleft()
			res.append(temp)
			for renei in re[temp]:
				graph[renei].remove(temp)
				if len(graph[renei]) == 0:
					q.append(renei)
		return sorted(res)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		ans = []
		if len(graph) == 0:
			return ans
		status = [0 for _ in range(len(graph))]
		for i in range(len(graph)):
			if status[i] == 0:
				self.dfs(i, graph, status, ans)
		ans.sort()
		return ans

	def dfs(self, i, graph, status, ans):
		status[i] = 1
		for neighbor in graph[i]:
			if status[neighbor] == 1:
				return False
			if status[neighbor] == 0 and (not self.dfs(neighbor, graph, status, ans)):
				return False
		status[i] = 2
		ans.append(i)
		return True


from collections import defaultdict

class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		g = defaultdict(list)
		for i in range(len(graph)):
			g[i] = graph[i]
		array = [False] * len(graph)
		visited = [False] * len(graph)
		for i in range(len(graph)):
			if visited[i] == False:
				self.dfs(i, graph, visited, array)
		ans = []
		for i in range(len(array)):
			if array[i] == True:
				ans.append(i)
		return ans

	def dfs(self, node, graph, visited, array):
		visited[node] = True
		if len(graph[node]) == 0:
			array[node] = True
		else:
			b = True
			for ver in graph[node]:
				if visited[ver] == False:
					self.dfs(ver, graph, visited, array)
				b = b & array[ver]
			array[node] = b


from collections import defaultdict

class Solution:

	def eventualSafeNodes(self, graph):
		state = defaultdict(int)

		def dfs(node):
			if state[node]:
				return state[node] == 2
			state[node] = 1
			for nei in graph[node]:
				if state[nei] == 1 or not dfs(nei):
					return False
			state[node] = 2
			return True
		N = len(graph)
		return [node for node in range(N) if dfs(node)]


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		visited = [False for i in range(len(graph))]
		recStack = [False for i in range(len(graph))]

		def dfs(node):
			visited[node] = True
			recStack[node] = True
			for nbor in graph[node]:
				if not visited[nbor]:
					if dfs(nbor):
						return True
				elif recStack[nbor]:
					return True
			recStack[node] = False
			return False
		res = []
		for vert in range(len(graph)):
			if not dfs(vert):
				res.append(vert)
		res.sort()
		return res


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		adj = {}
		for i in range(n):
			adj[i] = set(graph[i])
		safe = set()
		for i in range(n):
			if not adj[i]:
				safe.add(i)
		prev_size = len(safe)
		while True:
			for i in range(n):
				if i in safe:
					continue
				for x in adj[i]:
					if x not in safe:
						break
				else:
					safe.add(i)
			if len(safe) == prev_size:
				break
			else:
				prev_size = len(safe)
		out = []
		for i in range(n):
			if i in safe:
				out.append(i)
		return out


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		nodes = set()
		for i in range(len(graph)):
			if len(graph[i]) == 0:
				nodes.add(i)
		stop = False
		while not stop:
			tmp = set()
			for i in range(len(graph)):
				if i not in nodes:
					add = True
					for dest in graph[i]:
						if dest not in nodes:
							add = False
							break
					if add:
						tmp.add(i)
			if len(tmp) == 0:
				stop = True
			nodes = nodes.union(tmp)
		return sorted(nodes)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		(W, G, B) = (0, 1, 2)
		color = collections.defaultdict(int)

		def dfs(node):
			if color[node] != W:
				return color[node] == B
			color[node] = G
			for nei in graph[node]:
				if color[nei] == B:
					continue
				if color[nei] == G or not dfs(nei):
					return False
			color[node] = B
			return True
		res = []
		for i in range(len(graph)):
			if dfs(i):
				res.append(i)
		return res


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		visited = set()
		states = [None] * len(graph)

		def verify(i):
			if states[i] is not None:
				return states[i]
			if i in visited:
				return False
			visited.add(i)
			for j in graph[i]:
				stable = verify(j)
				if j in visited:
					visited.remove(j)
				states[j] = stable
				if not stable:
					return False
			return True
		verified_unstable = set()
		for i in range(len(graph)):
			if states[i] is not None:
				continue
			states[i] = verify(i)
		return [i for (i, val) in enumerate(states) if val == True]


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		color = [0] * len(graph)

		def df(v):
			if color[v] == 2:
				return True
			if color[v] == 1:
				return False
			color[v] = 1
			for v2 in graph[v]:
				if color[v2] == 1 or (color[v2] == 0 and (not df(v2))):
					return False
			color[v] = 2
			return True
		safe = []
		for v in range(len(graph)):
			if df(v):
				safe.append(v)
		return safe


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		g = defaultdict(list)
		result = []
		outDegre = [0] * len(graph)
		for i in range(len(graph)):
			outDegre[i] = len(graph[i])
			if not outDegre[i]:
				result.append(i)
			for j in graph[i]:
				g[j].append(i)
		print(outDegre)
		for nodes in result:
			for nei in g[nodes]:
				outDegre[nei] = outDegre[nei] - 1
				if outDegre[nei] == 0:
					result.append(nei)
		print(g)
		print(outDegre)
		return sorted(result)


class Solution(object):

	def eventualSafeNodes(self, graph):
		(WHITE, GRAY, BLACK) = (0, 1, 2)
		color = collections.defaultdict(int)

		def dfs(node):
			if color[node] != WHITE:
				return color[node] == BLACK
			color[node] = GRAY
			for nei in graph[node]:
				if color[nei] == BLACK:
					continue
				if color[nei] == GRAY or not dfs(nei):
					return False
			color[node] = BLACK
			return True
		return filter(dfs, range(len(graph)))


class Solution:

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

		def dfs(graph, node):
			if not graph[node]:
				return True
			if node not in self.dp:
				self.dp[node] = -1
				res = True
				for nex in graph[node]:
					res = res and dfs(graph, nex)
				self.dp[node] = res
			elif self.dp[node] == -1:
				return False
			return self.dp[node]
		self.dp = {}
		res = []
		for i in range(len(graph)):
			if dfs(graph, i):
				res.append(i)
		return res


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		visited = {}
		departures = [-1] * len(graph)
		res = []

		def _dfs(node):
			visited[node] = 1
			neighbors = graph[node]
			for neighbor in neighbors:
				if neighbor not in visited:
					if _dfs(neighbor):
						return True
				elif departures[neighbor] == -1:
					return True
			departures[node] = 1
			return False
		for i in range(0, len(graph)):
			if not _dfs(i):
				res.append(i)
		return res


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		res = set()
		for i in range(len(graph)):
			visited = set([i])
			self.dfs(graph, i, visited, res)
		return sorted(list(res))

	def dfs(self, graph, i, visited, res):
		for j in graph[i]:
			if j in visited:
				return False
			if j in res:
				continue
			visited.add(j)
			if not self.dfs(graph, j, visited, res):
				return False
			visited.remove(j)
		res.add(i)
		return True


from typing import Dict, List, Set

class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		result = []
		graph_map: Dict[int, Set[int]] = {}
		reverse_graph_map: Dict[int, Set[int]] = {}
		for (i, edges) in enumerate(graph):
			graph_map[i] = set(edges)
			for n in edges:
				reverse_graph_map.setdefault(n, set())
				reverse_graph_map[n].add(i)
		while True:
			to_remove = set()
			for (i, edges) in list(graph_map.items()):
				if len(edges) == 0:
					to_remove.add(i)
			if len(to_remove) == 0:
				break
			result.extend(to_remove)
			for i in to_remove:
				del graph_map[i]
				for n in reverse_graph_map.get(i, set()):
					graph_map[n].remove(i)
		return sorted(result)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		flags = [0] * len(graph)

		def dfs(node, visited):
			visited.add(node)
			for neighbor in graph[node]:
				if flags[neighbor] == 1:
					continue
				if flags[neighbor] == -1:
					return False
				if neighbor in visited or not dfs(neighbor, visited.copy()):
					flags[neighbor] = -1
					return False
			flags[node] = 1
			return True
		visited = set()
		for i in range(len(graph)):
			if not flags[i]:
				dfs(i, visited)
		return [i for (i, flag) in enumerate(flags) if flag == 1]


class Solution:

	def isCycle(self, src, graph: List[List[int]], visited):
		(WHITE, GRAY, BLACK) = (0, 1, 2)
		if visited[src] != WHITE:
			return visited[src] == GRAY
		stack = []
		stack.append((src, 1))
		stack.append((src, 0))
		while stack:
			current = stack.pop()
			if current[1] == 1:
				visited[current[0]] = BLACK
				continue
			current = current[0]
			visited[current] = GRAY
			for e in graph[current]:
				if visited[e] == GRAY:
					return True
				if visited[e] == WHITE:
					stack.append((e, 1))
					stack.append((e, 0))
		return False

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		eventualSafe = []
		visited = [0] * len(graph)
		for i in range(len(graph)):
			if not self.isCycle(i, graph, visited):
				eventualSafe.append(i)
		return eventualSafe


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		degree = [len(row) for row in graph]
		children = collections.defaultdict(list)
		for (i, row) in enumerate(graph):
			for j in row:
				children[j].append(i)
		seen = set()
		bfs = [i for i in range(len(degree)) if degree[i] == 0]
		for val in bfs:
			if val in seen:
				continue
			seen.add(val)
			for child in children[val]:
				degree[child] -= 1
				if not degree[child]:
					bfs.append(child)
		return sorted(list(seen))


class Solution:

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

		def explore(i):
			visited[i] = 0
			for v in graph[i]:
				if visited[v] == 0 or (visited[v] == -1 and explore(v)):
					return True
			visited[i] = 1
			res.append(i)
			return False
		(visited, res) = ([-1] * len(graph), [])
		for i in range(len(graph)):
			if visited[i] == -1:
				explore(i)
		return sorted(res)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		safe_nodes = set()
		for (i, node) in enumerate(graph):
			if len(node) == 0:
				safe_nodes.add(i)
		while True:
			starting_len = len(safe_nodes)
			for (i, node) in enumerate(graph):
				all_safe = True
				for j in node:
					if j not in safe_nodes:
						all_safe = False
						break
				if all_safe:
					safe_nodes.add(i)
			if starting_len == len(safe_nodes):
				break
		return sorted(list(safe_nodes))


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		out_degree = collections.defaultdict(int)
		inward_nodes = collections.defaultdict(list)
		for src in range(len(graph)):
			for child in graph[src]:
				inward_nodes[child].append(src)
				out_degree[src] += 1
		q = collections.deque()
		for i in range(len(graph)):
			if not i in out_degree:
				q.append(i)
		result = []
		while q:
			top = q.popleft()
			result.append(top)
			for parent in inward_nodes[top]:
				out_degree[parent] -= 1
				if out_degree[parent] == 0:
					q.append(parent)
		return sorted(result)


class Solution:
	data = {}

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		result = []
		self.data = {}
		for i in range(len(graph)):
			if i in self.data:
				if self.data[i]:
					result.append(i)
			else:
				res = self.check(graph, i, [])
				if res == True:
					result.append(i)
					self.data[i] = True
		return result

	def check(self, graph, curr, path):
		if curr in path:
			self.data[curr] = False
			for p in path:
				self.data[p] = False
			return False
		if len(graph[curr]) == 0:
			self.data[curr] = True
			return True
		result = True
		for n in graph[curr]:
			if n == curr:
				self.data[n] = False
				return False
			if n in self.data:
				result = result and self.data[n]
			else:
				res = self.check(graph, n, path + [curr])
				result = result and res
			if result == False:
				return False
		if result == True:
			self.data[curr] = True
		return True


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		out_degrees = [0] * n
		node_lsts = collections.defaultdict(list)
		queue = []
		for i in range(len(graph)):
			out_degrees[i] = len(graph[i])
			if out_degrees[i] == 0:
				queue.append(i)
			for j in graph[i]:
				node_lsts[j].append(i)
		for term_node in queue:
			for n in node_lsts[term_node]:
				out_degrees[n] -= 1
				if out_degrees[n] == 0:
					queue.append(n)
		return sorted(queue)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		state = ['UNPROCESSED'] * n

		def isAcyclic(node):
			if state[node] == 'PROCESSING':
				return False
			elif state[node] == 'PROCESSED':
				return True
			else:
				state[node] = 'PROCESSING'
				if any((not isAcyclic(nei) for nei in graph[node])):
					return False
				state[node] = 'PROCESSED'
				return True
		return list(filter(isAcyclic, list(range(n))))


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		(WHITE, GRAY, BLACK) = (0, 1, 2)
		color = {}
		for i in range(len(graph)):
			color[i] = WHITE

		def dfs(node):
			if color[node] != WHITE:
				return color[node] == BLACK
			color[node] = GRAY
			for nei in graph[node]:
				if color[nei] == BLACK:
					continue
				elif color[nei] == GRAY:
					return False
				elif not dfs(nei):
					return False
			color[node] = BLACK
			return True
		safe = []
		for i in range(len(graph)):
			if dfs(i):
				safe.append(i)
		return safe


class Solution:

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

		def cycle(index):
			if visited[index] == 1:
				return True
			if visited[index] == 2:
				return False
			visited[index] = 1
			for node in graph[index]:
				if cycle(node):
					return True
			visited[index] = 2
			return False
		visited = [0] * len(graph)
		for i in range(len(graph)):
			cycle(i)
		safe = []
		for i in range(len(graph)):
			if visited[i] == 2:
				safe.append(i)
		return safe


class Solution:

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

		def dfs(node):
			if node in terminalnodes:
				return True
			if node in visited:
				return False
			visited[node] = 1
			a = True
			for newnodes in graph[node]:
				a = a and dfs(newnodes)
			if a == True:
				terminalnodes.add(node)
				return True
			else:
				return False
		nodes = len(graph)
		m = []
		nonlocal terminalnodes
		terminalnodes = {i for i in range(nodes) if len(graph[i]) == 0}
		print(terminalnodes)
		nonlocal visited
		visited = {}
		for i in range(len(graph)):
			visited = {}
			a = dfs(i)
			if a == True:
				terminalnodes.add(i)
		if len(terminalnodes) == 0:
			return []
		t = list(terminalnodes)
		t.sort()
		return t


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		notSafe = set()
		safe = set()

		def isSafe(node, visited):
			if node in notSafe:
				return False
			if not graph[node]:
				return True
			if node in safe:
				return True
			visited.add(node)
			for child in graph[node]:
				if child in visited:
					notSafe.add(child)
					notSafe.add(node)
					return False
				if not isSafe(child, set(visited)):
					notSafe.add(child)
					notSafe.add(node)
					return False
			safe.add(node)
			return True
		out = []
		for i in range(len(graph)):
			if isSafe(i, set()):
				out += (i,)
		return out


class Solution:

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

		def dfs(i):
			if color[i] == 1:
				return False
			elif color[i] == 2:
				return True
			elif color[i] == 0:
				color[i] = 1
				for j in graph[i]:
					if not dfs(j):
						return False
				color[i] = 2
				ans.append(i)
				return True
		ans = []
		color = [0] * len(graph)
		for i in range(len(graph)):
			if color[i] == 0:
				dfs(i)
		return sorted(ans)


class Solution:

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

		def cycle(snode):
			if mem[snode] == -1:
				return True
			elif mem[snode] == 1:
				return False
			seen_path.add(snode)
			for e in graph[snode]:
				if e in seen_path:
					for n in seen_path:
						mem[n] = -1
					return True
				if e not in seen:
					seen.add(e)
					res = cycle(e)
					if res:
						return res
			mem[snode] = 1
			seen_path.discard(snode)
			return False
		ret = []
		seen = set()
		seen_path = set()
		mem = [0] * len(graph)
		for i in range(len(graph)):
			seen_path.clear()
			seen.clear()
			if not cycle(i):
				ret.append(i)
		return ret


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		terminal = []
		n = len(graph)
		visited = [-1] * n

		def dfs(i):
			visited[i] = 0
			for t in graph[i]:
				if visited[t] == 0 or (visited[t] == -1 and (not dfs(t))):
					return False
			visited[i] = 1
			terminal.append(i)
			return True
		for i in range(n):
			if visited[i] == -1:
				dfs(i)
		return sorted(terminal)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		graph = list(map(set, graph))
		rgraph = defaultdict(set)
		q = deque()
		for (i, nn) in enumerate(graph):
			if not nn:
				q.append(i)
			for j in nn:
				rgraph[j].add(i)
		res = []
		while q:
			j = q.popleft()
			res.append(j)
			for i in rgraph[j]:
				graph[i].remove(j)
				if not graph[i]:
					q.append(i)
		res.sort()
		return res


class Solution:

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

		def check_safe(graph, st, seen, cur):
			if st[cur] != 0:
				return st[cur]
			if len(graph[cur]) == 0:
				return 1
			if cur in seen:
				return -1
			seen.add(cur)
			for ne in graph[cur]:
				rtv = check_safe(graph, st, seen, ne)
				if rtv == -1:
					st[cur] = -1
					return -1
			seen.discard(cur)
			st[cur] = 1
			return 1
		N = len(graph)
		st = [0] * N
		for i in range(N):
			if st[i] != 0:
				continue
			seen = set()
			st[i] = check_safe(graph, st, seen, i)
		rtv = []
		for (i, s) in enumerate(st):
			if s == 1:
				rtv.append(i)
		return rtv


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		out_degree = [0] * n
		in_nodes = collections.defaultdict(list)
		queue = []
		for i in range(n):
			out_degree[i] = len(graph[i])
			if out_degree[i] == 0:
				queue.append(i)
			for j in graph[i]:
				in_nodes[j].append(i)
		for term_node in queue:
			for in_node in in_nodes[term_node]:
				out_degree[in_node] -= 1
				if out_degree[in_node] == 0:
					queue.append(in_node)
		return sorted(queue)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		res = []
		degree = [0] * n
		reverseGraph = collections.defaultdict(list)
		q = collections.deque()
		for i in range(n):
			if len(graph[i]) == 0:
				q.append(i)
			for nextNode in graph[i]:
				reverseGraph[nextNode].append(i)
				degree[i] += 1
		while q:
			index = q.popleft()
			res.append(index)
			for nextNode in reverseGraph[index]:
				degree[nextNode] -= 1
				if degree[nextNode] == 0:
					q.append(nextNode)
		return sorted(res)


from collections import defaultdict, deque

class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		(revadj, outdegree) = (defaultdict(list), dict())
		for (src, dsts) in enumerate(graph):
			for dst in dsts:
				revadj[dst].append(src)
			outdegree[src] = len(dsts)
		(q, res) = (deque([i for (i, d) in outdegree.items() if d == 0]), [])
		while q:
			dst = q.popleft()
			res.append(dst)
			for src in revadj[dst]:
				outdegree[src] -= 1
				if outdegree[src] == 0:
					q.append(src)
		return sorted(res)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		v = [0] * n

		def circle(i):
			if v[i] == 2:
				return False
			if v[i] == 1:
				return True
			v[i] = 1
			for nei in graph[i]:
				if circle(nei):
					return True
			v[i] = 2
			return False
		res = []
		for i in range(n):
			if circle(i):
				continue
			res.append(i)
		return res


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		safe = [False for _ in range(n)]
		rgraph = [set([]) for _ in range(n)]
		queue = collections.deque([])
		for i in range(n):
			if not graph[i]:
				queue.append(i)
			else:
				for j in graph[i]:
					rgraph[j].add(i)
		while queue:
			curr_node = queue.popleft()
			safe[curr_node] = True
			for prev in rgraph[curr_node]:
				graph[prev].remove(curr_node)
				if len(graph[prev]) == 0:
					queue.append(prev)
		return [i for (i, s) in enumerate(safe) if s]


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		(UNKNOWN, VISITING, VISITED) = (0, 1, 2)
		status = [UNKNOWN] * len(graph)

		def dfs(node):
			if status[node] == UNKNOWN:
				status[node] = VISITING
				if all([dfs(n) for n in graph[node]]):
					status[node] = VISITED
					return True
				else:
					return False
			elif status[node] == VISITED:
				return True
			elif status[node] == VISITING:
				return False
		for n in range(len(graph)):
			if status[n] == UNKNOWN:
				dfs(n)
		return sorted([x for (x, stat) in enumerate(status) if stat == VISITED])


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		dic = collections.defaultdict(list)
		for (i, e) in enumerate(graph):
			for j in e:
				dic[i].append(j)
		memo = {}

		def dfs(node):
			if not dic[node]:
				return True
			if node in memo:
				return memo[node]
			memo[node] = False
			if all((dfs(nxt) for nxt in dic[node])):
				memo[node] = True
			return memo[node]
		res = []
		for i in range(len(graph)):
			if dfs(i):
				res.append(i)
		return res


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		states = [0 for i in range(n)]

		def dfs(i):
			if states[i] != 0:
				return states[i]
			if not graph[i]:
				states[i] = 2
				return states[i]
			states[i] = 1
			eventual_state = 2
			for j in graph[i]:
				if states[j] == 0:
					state_j = dfs(j)
				else:
					state_j = states[j]
				eventual_state = min(state_j, eventual_state)
			states[i] = eventual_state
			return states[i]
		output = []
		for i in range(n):
			s = dfs(i)
			if s == 2:
				output.append(i)
		return sorted(output)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		adj = defaultdict(list)
		degree = dict()
		for (i, node) in enumerate(graph):
			degree[i] = len(node)
			for n in node:
				adj[n].append(i)
		bfs = deque([x for (x, count) in degree.items() if count == 0])
		result = []
		while bfs:
			current = bfs.popleft()
			result.append(current)
			for n in adj[current]:
				degree[n] -= 1
				if degree[n] == 0:
					bfs.append(n)
		return sorted(result)


from collections import defaultdict

class Solution:

	def dfs(self, node, graph, eventuallySafe, visited):
		if node in eventuallySafe:
			return True
		if node in visited:
			return False
		visited.add(node)
		adjNodes = graph[node]
		if len(adjNodes) != 0:
			isEventuallySafe = True
			for neighbour in adjNodes:
				isEventuallySafe = self.dfs(neighbour, graph, eventuallySafe, visited) and isEventuallySafe
			if not isEventuallySafe:
				return False
		eventuallySafe.add(node)
		return True

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		eventuallySafe = set()
		visited = set()
		for n in range(len(graph)):
			self.dfs(n, graph, eventuallySafe, visited)
		return sorted(list(eventuallySafe))


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		adj_list = defaultdict(list)
		vertices_with_no_incoming_edges = []
		stack = deque()
		indegree_graph = defaultdict(int)
		vertices_part_of_cycle = []
		no_of_vertices = len(graph)
		for i in range(no_of_vertices):
			indegree_graph[i] = 0
		for source in range(no_of_vertices):
			for dest in graph[source]:
				adj_list[dest].append(source)
				indegree_graph[source] += 1
		for (key, val) in indegree_graph.items():
			if indegree_graph[key] == 0:
				stack.append(key)
				vertices_with_no_incoming_edges.append(key)
		while stack:
			vert = stack.pop()
			if vert in adj_list:
				for v in adj_list[vert]:
					indegree_graph[v] -= 1
					if indegree_graph[v] == 0:
						vertices_with_no_incoming_edges.append(v)
						stack.append(v)
		return sorted(vertices_with_no_incoming_edges)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		(WHITE, GREY, BLACK) = (0, 1, 2)
		result = []
		color = defaultdict()
		for i in range(len(graph)):
			color[i] = WHITE

		def dfs(node):
			if color[node] != WHITE:
				return color[node] == BLACK
			color[node] = GREY
			for neigh in graph[node]:
				if not dfs(neigh):
					return False
			color[node] = BLACK
			return True
		for i in range(len(graph)):
			if not graph[i]:
				result.append(i)
			elif dfs(i):
				result.append(i)
		return result


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		graph_reverse = collections.defaultdict(list)
		indegree = collections.defaultdict(int)
		for i in range(len(graph)):
			if not graph[i]:
				indegree[i]
			for nei in graph[i]:
				graph_reverse[nei].append(i)
				indegree[nei]
				indegree[i] += 1
		q = collections.deque([node for node in indegree if indegree[node] == 0])
		res = []
		while q:
			node = q.popleft()
			res.append(node)
			for nei in graph_reverse[node]:
				indegree[nei] -= 1
				if indegree[nei] == 0:
					q.append(nei)
		return sorted(res)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		nodes = reduce(lambda node, e: node[e[0]].extend(e[1]) or node, enumerate(graph), defaultdict(list))
		visited = set()
		s = set()

		def dfs(i):
			if i in s:
				return False
			if i in visited:
				return True
			s.add(i)
			if not all(map(dfs, nodes[i])):
				return False
			s.remove(i)
			visited.add(i)
			return True
		return [i for i in range(len(graph)) if dfs(i)]


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		deg = {}
		grev = {}
		terminals = []
		for i in range(n):
			deg[i] = len(graph[i])
			if deg[i] == 0:
				terminals.append(i)
			for j in graph[i]:
				if j not in grev:
					grev[j] = []
				grev[j].append(i)
		for t in terminals:
			if t not in grev:
				continue
			for j in grev[t]:
				deg[j] -= 1
				if deg[j] == 0:
					terminals.append(j)
		return sorted(terminals)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		safe = set()
		revg = defaultdict(set)
		q = deque()
		graph = list(map(set, graph))
		for (u, nodes) in enumerate(graph):
			if not nodes:
				q.append(u)
			for v in nodes:
				revg[v].add(u)
		while q:
			temp = q.popleft()
			safe.add(temp)
			for v in revg[temp]:
				graph[v].remove(temp)
				if not graph[v]:
					q.append(v)
		return sorted(safe)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		ans = []

		def dfs(node):
			if arr[node] != -1:
				return arr[node] == 1
			arr[node] = 0
			for j in graph[node]:
				if arr[j] == 1:
					continue
				elif arr[j] == 0 or not dfs(j):
					return False
			arr[node] = 1
			return True
		arr = [-1] * n
		for i in range(n):
			if len(graph[i]) == 0:
				ans.append(i)
				continue
			if dfs(i):
				ans.append(i)
		return ans


class Solution:

	def eventualSafeNodes(self, graph):
		degrees = {}
		(safe, unsafe) = (set(), set())
		adj = {}
		for node in range(len(graph)):
			nodes = graph[node]
			degrees[node] = len(nodes)
			graph[node] = set(nodes)
			if node not in adj:
				adj[node] = set()
			for another in nodes:
				if another not in adj:
					adj[another] = set()
				adj[another].add(node)
		queue = []
		for node in degrees:
			if degrees[node] == 0:
				queue.append(node)
		while True:
			if len(queue) == 0:
				break
			node = queue.pop()
			if degrees[node] == 0:
				safe.add(node)
				for another in adj[node]:
					degrees[another] -= 1
					if degrees[another] == 0 and another not in safe:
						queue.append(another)
			else:
				break
		safe = list(safe)
		safe.sort()
		return safe


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		ans = []
		N = len(graph)
		out = collections.defaultdict(set)
		in_cnt = [0 for _ in range(N)]
		ready = set(range(N))
		for end in range(N):
			for start in graph[end]:
				out[start].add(end)
				in_cnt[end] += 1
				if end in ready:
					ready.remove(end)
		while len(ready) > 0:
			rm = ready.pop()
			ans.append(rm)
			for nei in out[rm]:
				in_cnt[nei] -= 1
				if in_cnt[nei] == 0:
					ready.add(nei)
		return sorted(ans)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		cycle = set()
		used = set()

		def do(cur, path=set()):
			if cur in used:
				return True
			if cur in cycle or cur in path:
				return False
			for nxt in graph[cur]:
				if not do(nxt, path | {cur}):
					cycle.update({cur, nxt})
					return False
			used.add(cur)
			return True
		return list(filter(do, range(len(graph))))


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		new_g = {i: [] for i in range(len(graph))}
		for (i, n) in enumerate(graph):
			new_g[i].append(n)

		def dfs(n):
			if status[n] == -1:
				return False
			if status[n] == 1:
				return True
			status[n] = -1
			for adj in graph[n]:
				if not dfs(adj):
					return False
			status[n] = 1
			return True
		status = [0 for _ in range(len(graph))]
		return filter(dfs, range(len(graph)))


from collections import defaultdict

class Solution:

	def eventualSafeNodes(self, graph):
		state = defaultdict(int)

		def dfs(node):
			if state[node] == 1:
				state[node] = 3
				return 3
			if state[node]:
				return state[node]
			state[node] = 1
			for nei in graph[node]:
				if dfs(nei) == 3:
					state[node] = 3
					return 3
			state[node] = 2
			return 2
		N = len(graph)
		return [node for node in range(N) if dfs(node) == 2]


from collections import defaultdict, deque

class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		degree = [len(graph[i]) for i in range(len(graph))]
		edges = defaultdict(list)
		for i in range(len(graph)):
			for j in graph[i]:
				edges[j].append(i)
		q = deque()
		for i in range(len(graph)):
			if degree[i] == 0:
				q.append(i)
		res = []
		while q:
			node = q.popleft()
			res.append(node)
			for n in edges[node]:
				degree[n] -= 1
				if degree[n] == 0:
					q.append(n)
		return sorted(res)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		perm = {i for (i, e) in enumerate(graph) if not e}
		rev = [[] for i in range(len(graph))]
		for (i, e) in enumerate(graph):
			for j in e:
				rev[j].append(i)
		last = perm.copy()
		while last:
			tmp = set()
			for n in last:
				for nei in rev[n]:
					if nei not in perm and all((cat in perm for cat in graph[nei])):
						tmp.add(nei)
			perm = perm.union(tmp)
			last = tmp
		return sorted(perm)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		unsafe_nodes = set()
		safe_nodes = set()

		def dfs(node, visited):
			if node in visited:
				return False
			visited.add(node)
			for neighbor in graph[node]:
				if neighbor in unsafe_nodes:
					unsafe_nodes.add(node)
					return False
				if neighbor in safe_nodes:
					continue
				if not dfs(neighbor, visited):
					unsafe_nodes.add(node)
					return False
			safe_nodes.add(node)
			return True
		safe = []
		for i in range(len(graph)):
			if dfs(i, set()):
				safe.append(i)
		return safe


class Solution:

	def __init__(self):
		self.safe_nodes = set()
		self.unsafe_nodes = set()

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

		def is_safe(node, stack=[]):
			if not graph[node] or node in self.safe_nodes:
				self.safe_nodes.add(node)
				return True
			elif node in self.unsafe_nodes:
				return False
			else:
				if node in stack:
					self.unsafe_nodes |= set(stack)
					return False
				stack.append(node)
				if all([is_safe(child) for child in graph[node]]):
					self.safe_nodes.add(node)
					stack.pop()
					return True
				else:
					self.unsafe_nodes.add(node)
					stack.pop()
					return False
		for node in range(len(graph)):
			is_safe(node)
		return sorted(list(self.safe_nodes))


from collections import defaultdict, deque

class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		q = deque()
		ans = [False] * n
		graph_map = dict()
		r_graph_map = defaultdict(set)
		for i in range(n):
			graph_map[i] = set(graph[i])
			if not graph[i]:
				q.append(i)
			for out in graph[i]:
				r_graph_map[out].add(i)
		while q:
			safe_i = q.popleft()
			ans[safe_i] = True
			for in_id in r_graph_map[safe_i]:
				graph_map[in_id].remove(safe_i)
				if len(graph_map[in_id]) == 0:
					q.append(in_id)
		return [i for (i, safe) in enumerate(ans) if safe]


from collections import deque

class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		N = len(graph)
		graph = list(map(set, graph))
		rgraph = [set() for _ in range(N)]
		safe = [False] * N
		q = deque()
		for (fr, tos) in enumerate(graph):
			if not tos:
				q.append(fr)
			for to in tos:
				rgraph[to].add(fr)
		while q:
			to = q.popleft()
			safe[to] = True
			for fr in rgraph[to]:
				graph[fr].remove(to)
				if not graph[fr]:
					q.append(fr)
		return [i for (i, v) in enumerate(safe) if v]


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		(SAFE, VISITED, UNSAFE) = (1, 0, -1)
		is_safe = [None] * len(graph)

		def explore(node):
			if not graph[node]:
				is_safe[node] = SAFE
				return
			if is_safe[node] == VISITED:
				is_safe[node] = UNSAFE
				return
			if is_safe[node] == None:
				is_safe[node] = VISITED
				for child in graph[node]:
					if is_safe[child] in [None, VISITED]:
						explore(child)
					if is_safe[child] == UNSAFE:
						is_safe[node] = UNSAFE
						return
				else:
					is_safe[node] = SAFE
					return
		for node in range(len(graph)):
			if is_safe[node] == None:
				explore(node)
		return [node for node in range(len(graph)) if is_safe[node] == SAFE]


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		cycle_nodes = set()
		safe_nodes = set()
		visited = set()

		def helper(node: int, visited: set) -> bool:
			if node in cycle_nodes:
				return False
			if node in safe_nodes:
				return True
			if node in visited:
				cycle_nodes.add(node)
				return False
			visited.add(node)
			for child in graph[node]:
				if helper(child, visited) is False:
					cycle_nodes.add(node)
					return False
			safe_nodes.add(node)
			return True
		ans = []
		for node in range(len(graph)):
			if helper(node, visited):
				ans.append(node)
		return ans


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		ev_safe = collections.deque()
		sgraph = defaultdict(set)
		rgraph = defaultdict(set)
		safe = [False] * len(graph)
		for (i, nei) in enumerate(graph):
			if not nei:
				ev_safe.append(i)
			for out in nei:
				rgraph[out].add(i)
				sgraph[i].add(out)
		while ev_safe:
			node_point2safe = ev_safe.popleft()
			safe[node_point2safe] = True
			for node in rgraph[node_point2safe]:
				graph[node].remove(node_point2safe)
				if len(graph[node]) == 0:
					ev_safe.append(node)
		return [i for (i, v) in enumerate(safe) if v]


def f(x, y, ci, v):
	a = True
	for i in x[ci]:
		if i in v:
			if y[i] != 1:
				a = False
			continue
		v.add(i)
		y[i] = f(x, y, i, v)
		a = y[i] and a
	return a

class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		l = len(graph)
		y = [-1 for i in range(l)]
		v = set()
		for i in range(l):
			if y[i] == -1:
				v.add(i)
				y[i] = f(graph, y, i, v)
		return [i for i in range(l) if y[i]]


class Solution:

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

		def dfs(node, graph):
			nodes[node] = 1
			for child in graph[node]:
				if nodes[child] == 1:
					return False
				if not nodes[child] and (not dfs(child, graph)):
					return False
			nodes[node] = 2
			return True
		nodes = [0 for _ in range(len(graph))]
		ans = []
		for node in range(len(graph)):
			if dfs(node, graph):
				ans.append(node)
		return ans


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		v = [0 for _ in range(len(graph))]
		ans = []

		def dfs(cur):
			if v[cur] == 1:
				return True
			if v[cur] == 2:
				return False
			v[cur] = 1
			for j in graph[cur]:
				if dfs(j):
					return True
			v[cur] = 2
			return False
		for i in range(len(graph)):
			if dfs(i):
				continue
			else:
				ans.append(i)
		return ans


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		(WHITE, GREY, BLACK) = (0, 1, 2)
		color = collections.defaultdict(int)

		def dfs(u):
			if color[u] != WHITE:
				return color[u] != GREY
			color[u] = GREY
			for v in graph[u]:
				if color[v] == BLACK:
					continue
				if color[v] == GREY or not dfs(v):
					return False
			color[u] = BLACK
			return True
		return list(filter(dfs, range(len(graph))))


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		colour = [-1] * n

		def dfs(u):
			if colour[u] != -1:
				colour[u] = 1
			colour[u] = 0
			for nei in graph[u]:
				if colour[nei] == 1:
					continue
				if colour[nei] == 0 or not dfs(nei):
					return False
			colour[u] = 1
			return True
		return list(filter(dfs, list(range(n))))


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		result = []
		indegree = [len(edge) for edge in graph]
		neighbors = collections.defaultdict(list)
		for (i, edge) in enumerate(graph):
			for j in edge:
				neighbors[j].append(i)
		queue = []
		for i in range(n):
			if indegree[i] == 0:
				queue.append(i)
		while queue:
			i = queue.pop(0)
			result.append(i)
			for neighbor in neighbors[i]:
				indegree[neighbor] -= 1
				if indegree[neighbor] == 0:
					queue.append(neighbor)
		return sorted(result)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		color = [0] * n

		def dfs(node):
			if color[node]:
				return color[node] == 2
			color[node] = 1
			for nbor in graph[node]:
				if not dfs(nbor):
					return False
			color[node] = 2
			return True
		return [node for node in range(n) if dfs(node)]


class Solution:

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

		def cycle(ind):
			if color[ind] == 1:
				return True
			if color[ind] == 2:
				return False
			color[ind] = 1
			for node in graph[ind]:
				if cycle(node):
					return True
			color[ind] = 2
			return False
		n = len(graph)
		color = [0] * n
		for i in range(len(graph)):
			cycle(i)
		return [i for i in range(n) if color[i] == 2]


class Solution:

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

		def dfs(i):
			if color[i] != 0:
				return color[i]
			color[i] = 1
			if any((dfs(j) == 1 for j in graph[i])):
				return color[i]
			color[i] = 2
			return color[i]
		color = collections.defaultdict(int)
		ans = []
		n = len(graph)
		for i in range(n):
			if dfs(i) == 2:
				ans.append(i)
		return ans


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		size = len(graph)
		AVAILABLE = 0
		VISITING = 1
		VISITED = 2
		status = [AVAILABLE] * size

		def isSafe(source, res):
			if status[source] != AVAILABLE:
				return status[source] == VISITED
			status[source] = VISITING
			for neighbour in graph[source]:
				if not isSafe(neighbour, res):
					return False
			status[source] = VISITED
			res.append(source)
			return True
		res = []
		for node in range(size):
			isSafe(node, res)
		return sorted(res)


from collections import defaultdict

class Solution:

	def eventualSafeNodes(self, edges: List[List[int]]) -> List[int]:
		graph = defaultdict(set)
		inv = defaultdict(set)
		N = len(edges)
		ret = set()
		for (s, es) in enumerate(edges):
			for e in es:
				graph[s].add(e)
				inv[e].add(s)
		for n in range(N):
			if len(graph[n]) == 0:
				ret.add(n)
		todo = set(ret)
		while todo:
			pending = set()
			for n in todo:
				for s in inv[n]:
					if graph[s].issubset(ret):
						ret.add(s)
						pending.add(s)
			todo = pending
		return sorted(ret)


from typing import List, Dict, Set
from collections import defaultdict

def find_safe_nodes(graph: Dict, rev_graph: Dict):
	outcount_nodes = defaultdict(set)
	for (node, list_innodes) in list(graph.items()):
		count_outedges = len(list_innodes)
		outcount_nodes[count_outedges].add(node)
	safe_nodes = set()
	while len(outcount_nodes[0]) > 0:
		safe_node = outcount_nodes[0].pop()
		safer_nodes = rev_graph[safe_node]
		for safer_node in safer_nodes:
			prev_outcount = len(graph[safer_node])
			graph[safer_node].remove(safe_node)
			outcount_nodes[prev_outcount].remove(safer_node)
			outcount_nodes[prev_outcount - 1].add(safer_node)
		safe_nodes.add(safe_node)
	return safe_nodes

class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		list_graph = graph
		graph = defaultdict(set)
		rev_graph = defaultdict(set)
		for (node1, list_node2) in enumerate(list_graph):
			for node2 in list_node2:
				graph[node1].add(node2)
				rev_graph[node2].add(node1)
		for i in range(len(list_graph)):
			if i not in graph:
				graph[i] = set()
			if i not in rev_graph:
				rev_graph[i] = set()
		safe_nodes = find_safe_nodes(graph, rev_graph)
		return sorted(safe_nodes)
s = Solution()
print(s.eventualSafeNodes(graph=[[1, 2], [2, 3], [5], [0], [5], [], []]))
print(s.eventualSafeNodes(graph=[[1, 2], [2, 3], [5], [0], [5], [], []]) == [2, 4, 5, 6])
print(s.eventualSafeNodes([[], [0, 2, 3, 4], [3], [4], []]))
print(s.eventualSafeNodes([[], [0, 2, 3, 4], [3], [4], []]) == [0, 1, 2, 3, 4])


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		parent_g = collections.defaultdict(list)
		visited = set()
		queue = []
		for i in range(len(graph)):
			if len(graph[i]) == 0:
				queue.append(i)
			for c in graph[i]:
				parent_g[c].append(i)
		while queue:
			current = queue.pop(0)
			flag = True
			for c in graph[current]:
				if not c in visited:
					flag = False
					break
			if flag:
				visited.add(current)
				for p in parent_g[current]:
					if not p in visited:
						queue.append(p)
		return sorted(list(visited))


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		(ans, dp, visited) = ([], {}, set())

		def dfs_visit(i):
			if i in visited:
				return False
			if i in dp:
				return dp[i]
			visited.add(i)
			valid = True
			if graph[i]:
				valid = all([dfs_visit(j) for j in graph[i]])
			visited.remove(i)
			dp[i] = valid
			return valid
		for i in range(len(graph)):
			if dfs_visit(i):
				ans.append(i)
		return ans


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		(w, g, b) = (0, 1, 2)
		color = collections.defaultdict(int)

		def dfs(node):
			if color[node] != w:
				return color[node] == b
			color[node] = g
			for child in graph[node]:
				if color[child] == b:
					continue
				elif color[child] == g or not dfs(child):
					return False
			color[node] = b
			return True
		ans = []
		for i in range(len(graph)):
			if dfs(i) == True:
				ans.append(i)
		return ans


import collections

class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		(WHITE, GRAY, BLACK) = (0, 1, 2)
		color_of_nodes = collections.defaultdict(int)

		def dfs(node):
			if color_of_nodes[node] != WHITE:
				return color_of_nodes[node] == BLACK
			color_of_nodes[node] = GRAY
			for nei in graph[node]:
				if color_of_nodes[nei] == GRAY or not dfs(nei):
					return False
			color_of_nodes[node] = BLACK
			return True
		res = []
		for (i, node) in enumerate(graph):
			if dfs(i):
				res.append(i)
		return res


class Solution(object):

	def eventualSafeNodes(self, graph):
		N = len(graph)
		T = set([n for n in range(N) if not graph[n]])
		V = set()

		def dfs(node, visited):
			if node in T:
				return True
			if node in V or node in visited:
				return False
			visited.append(node)
			for n in graph[node]:
				if not dfs(n, visited):
					V.add(node)
					V.add(n)
					return False
				else:
					T.add(n)
			T.add(node)
			return True
		res = [n for n in range(N) if dfs(n, [])]
		return res


class Solution:

	def __init__(self):
		self.d = {}
		self.safe_nodes = {}

	def safe_finder(self, cur_node):
		if len(self.d[cur_node]) == 0:
			self.safe_nodes[cur_node] = True
			return True
		for n in self.d[cur_node]:
			print(cur_node, n)
			if n == cur_node:
				self.safe_nodes[cur_node] = False
				return False
			if n in self.safe_nodes.keys():
				if self.safe_nodes[n] == False:
					self.safe_nodes[cur_node] = False
					return False
			else:
				self.safe_nodes[n] = False
				tmp = Solution.safe_finder(self, n)
				if tmp == False:
					self.safe_nodes[cur_node] = False
					return False
		self.safe_nodes[cur_node] = True
		return True

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		for i in range(len(graph)):
			node = graph[i]
			self.d[i] = []
			for edge in node:
				self.d[i].append(edge)
		for k in self.d.keys():
			Solution.safe_finder(self, k)
		answer = []
		for (k, v) in self.safe_nodes.items():
			if v == True:
				answer.append(k)
		return sorted(answer)


from collections import deque, defaultdict

class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		N = len(graph)
		safe_states = [False] * N
		another_graph = defaultdict(set)
		q = collections.deque()
		for (i, js) in enumerate(graph):
			if not js:
				q.append(i)
			for j in js:
				another_graph[j].add(i)
		print((graph, another_graph))
		while q:
			u = q.popleft()
			safe_states[u] = True
			for v in another_graph[u]:
				graph[v].remove(u)
				if len(graph[v]) == 0:
					q.append(v)
		return [u for (u, v) in enumerate(safe_states) if v]


from collections import deque

class Solution:

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

		def explore(i):
			colors[i] = 1
			for j in graph[i]:
				if colors[j] == 0 and explore(j) or colors[j] == 1:
					return True
			colors[i] = 2
			res.append(i)
			return False
		colors = [0 for i in range(len(graph))]
		res = []
		for i in range(len(graph)):
			if colors[i] == 0:
				explore(i)
		return sorted(res)


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		g = dict(enumerate(graph))
		safe = [-1] * len(g)

		def dfs(v):
			if safe[v] >= 0:
				return safe[v]
			if v not in g:
				safe[v] = 0
				return 0
			children = g.pop(v)
			if all(map(dfs, children)):
				safe[v] = 1
				return 1
			safe[v] = 0
			return 0
		for i in range(len(g)):
			dfs(i)
		return [i for (i, s) in enumerate(safe) if s > 0]


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		m = len(graph)
		color = [0] * m

		def dfs(i):
			if color[i]:
				return color[i] == 1
			color[i] = 2
			for n in graph[i]:
				if not dfs(n):
					return False
			color[i] = 1
			return True
		output = []
		for i in range(m):
			if dfs(i):
				output.append(i)
		return output


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		colour = [0] * len(graph)

		def dfs(i):
			if colour[i] != 0:
				return colour[i] == 2
			colour[i] = 1
			for c in graph[i]:
				if not dfs(c):
					return False
			colour[i] = 2
			return True
		for node in range(len(graph)):
			dfs(node)
		return [i for i in range(len(graph)) if colour[i] == 2]


import collections

class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		res = []
		visited = collections.defaultdict(int)
		N = len(graph)
		for i in range(N):
			if self.dfs(graph, i, visited):
				res.append(i)
		return res

	def dfs(self, graph, node, visited):
		if visited[node] == 1:
			return False
		if visited[node] == 2:
			return True
		visited[node] = 1
		for n in graph[node]:
			if not self.dfs(graph, n, visited):
				return False
		visited[node] = 2
		return True


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		n = len(graph)
		color = [0 for _ in range(n)]
		res = []
		for node_index in range(n):
			if self.dfs(graph, index=node_index, color=color):
				res.append(node_index)
		return res

	def dfs(self, graph, index, color):
		if color[index] > 0:
			return color[index] == 2
		color[index] = 1
		for j in graph[index]:
			if color[j] == 2:
				continue
			elif color[j] == 1 or not self.dfs(graph, j, color):
				return False
		color[index] = 2
		return True


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		safe = [False] * len(graph)
		rev = [set() for _ in range(len(graph))]
		queue = collections.deque()
		for (i, nodes) in enumerate(graph):
			if not nodes:
				queue.append(i)
			else:
				for node in nodes:
					rev[node].add(i)
		while queue:
			curr = queue.popleft()
			safe[curr] = True
			for j in rev[curr]:
				graph[j].remove(curr)
				if len(graph[j]) == 0:
					queue.append(j)
		return [i for (i, val) in enumerate(safe) if val]


class Solution:

	def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
		(seen, safe) = (set(), set())

		def dfs(u):
			if u in seen:
				return u in safe
			seen.add(u)
			if all((dfs(v) for v in graph[u])):
				safe.add(u)
				return True
		return list(filter(lambda u: dfs(u), range(len(graph))))