1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
# 802. Find Eventual Safe States
from collections import defaultdict
"""
there is a directed graph of 'n' nodes with each node labeled from 0 to n
- 1. the graph is represented by a 0-indexed 2d integer array 'graph' where
'graph[i]' is an integer array of nodes adjacent to node 'i', meaning there
is an edge from node 'i' to each node in 'graph[i]'. 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 ( or another safe
node). return an array containing all the safe nodes of the graph. the answer
should be sorted in ascending order.
"""
class Solution(object):
def eventualSafeNodes(self, graph):
"""
:type graph: List[List[int]]
:rtype: List[int]
"""
n = len(graph)
g = defaultdict(list)
dp = [0] * n
for i, v in enumerate(graph):
dp[i] = len(v)
for e in v:
g[e].append(i)
q = [i for i in range(n) if dp[i] == 0]
while q:
x = q.pop()
for e in g[x]:
dp[e] -= 1
if dp[e] == 0:
q.append(e)
ans = [i for i in range(n) if dp[i] == 0]
return ans
if __name__ == "__main__":
obj = Solution()
print(obj.eventualSafeNodes(graph=[[1, 2], [2, 3], [5], [0], [5], [], []]))
print(obj.eventualSafeNodes(graph=[[1, 2, 3, 4], [1, 2], [3, 4], [0, 4], []]))
|