-
Notifications
You must be signed in to change notification settings - Fork 0
/
dfs_802_graph_eventualSafeNodes.py
56 lines (50 loc) · 1.8 KB
/
dfs_802_graph_eventualSafeNodes.py
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
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution:
def eventualSafeNodes(self, graph):
""" input: graph: List[List[int]]
output: List[int]
"""
WHITE, GRAY, BLACK = 0, 1, 2
color = [0] * len(graph)
def dfs(node):
# terminate condition
if color[node] != WHITE:
# if this node has been visited
return color[node] == BLACK
# visit this node
color[node] = GRAY
# search deeper
for next_node in graph[node]:
if color[next_node] == BLACK:
continue # search for next neighbor
if color[next_node] == GRAY:
return False # next node has been visited
if not dfs(next_node):
return False # from next node, result in cycle
color[node] = BLACK
return True # this node is safe
for i in range(len(graph)):
dfs(i)
res = []
for i in range(len(color)):
if color[i]==BLACK:
res.append(i)
return res
def eventualSafeNodes_v2(self, graph):
# reverse graph for topo sort
rev_graph = [[] for _ in range(len(graph))]
safe = [False] * len(graph)
q = []
for st in range(len(graph)):
if len(graph[st])==0:
q.append(st) # if is end node, it's safe
for ed in graph[st]:
rev_graph[ed].append(st)
while len(q) > 0:
j = q.pop(0)
safe[j] = True
for i in rev_graph[j]:
graph[i].remove(j)
if len(graph[i]) == 0:
q.append(i)
safe[i] = True
return [i for i,v in enumerate(safe) if v]