Leetcode 802 Find Eventual Safe States

description

分析:
这道题是要在一个图里找不在环路中的节点,显然,dfs遍历即可,不过这里用拓扑排序方法也可以做,因为dfs这个方法我掌握得还不太熟练,老出各种小错误,等我钻研更深之后再补上dfs方法

思路:
记录下每个节点的出度,如果出度为0那必然是环路外的节点,然后将该点以及指向该点的边删除,继续寻找出度为0的点

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
class Solution(object):
def eventualSafeNodes(self, graph):
"""
:type graph: List[List[int]]
:rtype: List[int]
"""
if not graph: return []

n = len(graph)
# 用字段存储每个节点的父节点
d = {u:[] for u in range(n)}
degree = [0] * n
for u in range(n):
for v in graph[u]:
d[v].append(u)
degree[u] = len(graph[u])

Q = [u for u in range(n) if degree[u]==0]
res = []
while Q:
node = Q.pop()
res.append(node)
for nodes in d[node]:
degree[nodes] -= 1
if degree[nodes] == 0:
Q.append(nodes)
return sorted(res)