在下几百年没写DFS了
狗屎一般的写法
早用拓ㄆ排序
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
n = len(graph)
flag = [1 if len(graph[i])==0 else 0 for i in range(n)]
visited = [0 for _ in range(n)]
def dfs(cur) -> int:
if flag[cur] != 0:
return flag[cur]
if visited[cur] == 1:
flag[cur] = -1
return flag[cur]
visited[cur] = 1
cur_traversal = []
for node in graph[cur]:
cur_traversal.append(dfs(node))
if all([f==1 for f in cur_traversal]):
flag[cur] = 1
return 1
if any([f==-1 for f in cur_traversal]):
flag[cur] = -1
return -1
return 2
ans = []
for i in range(n):
if dfs(i)==1:
ans.append(i)
return ans