- 标签：深度优先搜索、广度优先搜索、图、拓扑排序
- 难度：中等
题目大意
#
描述：给定一个有向图 $graph$，其中 $graph[i]$ 是与节点 $i$ 相邻的节点列表，意味着从节点 $i$ 到节点 $graph[i]$ 中的每个节点都有一条有向边。
要求：找出图中所有的安全节点，将其存入数组作为答案返回，答案数组中的元素应当按升序排列。
说明：
- 终端节点：如果一个节点没有连出的有向边，则它是终端节点。或者说，如果没有出边，则节点为终端节点。
- 安全节点：如果从该节点开始的所有可能路径都通向终端节点，则该节点为安全节点。
- $n == graph.length$。
- $1 \le n \le 10^4$。
- $0 \le graph[i].length \le n$。
- $0 \le graph[i][j] \le n - 1$。
- $graph[i]$ 按严格递增顺序排列。
- 图中可能包含自环。
- 图中边的数目在范围 $[1, 4 \times 10^4]$ 内。
示例：
1
2
3
4
5
|
输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出：[2,4,5,6]
解释：示意图如上。
节点 5 和节点 6 是终端节点，因为它们都没有出边。
从节点 2、4、5 和 6 开始的所有路径都指向节点 5 或 6。
|
1
2
3
4
|
输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
输出：[4]
解释:
只有节点 4 是终端节点，从节点 4 开始的所有路径都通向节点 4。
|
解题思路
#
思路 1：拓扑排序
#
- 根据题意可知，安全节点所对应的终点，一定是出度为 $0$ 的节点。而安全节点一定能在有限步内到达终点，则说明安全节点一定不在「环」内。
- 我们可以利用拓扑排序来判断顶点是否在环中。
- 为了找出安全节点，可以采取逆序建图的方式，将所有边进行反向。这样出度为 $0$ 的终点就变为了入度为 $0$ 的点。
- 然后通过拓扑排序不断移除入度为 $0$ 的点之后，如果不在「环」中的点，最后入度一定为 $0$，这些点也就是安全节点。而在「环」中的点，最后入度一定不为 $0$。
- 最后将所有安全的起始节点存入数组作为答案返回。
思路 1：代码
#
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
|
class Solution:
# 拓扑排序，graph 中包含所有顶点的有向边关系（包括无边顶点）
def topologicalSortingKahn(self, graph: dict):
indegrees = {u: 0 for u in graph} # indegrees 用于记录所有节点入度
for u in graph:
for v in graph[u]:
indegrees[v] += 1 # 统计所有节点入度
# 将入度为 0 的顶点存入集合 S 中
S = collections.deque([u for u in indegrees if indegrees[u] == 0])
while S:
u = S.pop() # 从集合中选择一个没有前驱的顶点 0
for v in graph[u]: # 遍历顶点 u 的邻接顶点 v
indegrees[v] -= 1 # 删除从顶点 u 出发的有向边
if indegrees[v] == 0: # 如果删除该边后顶点 v 的入度变为 0
S.append(v) # 将其放入集合 S 中
res = []
for u in indegrees:
if indegrees[u] == 0:
res.append(u)
return res
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
graph_dict = {u: [] for u in range(len(graph))}
for u in range(len(graph)):
for v in graph[u]:
graph_dict[v].append(u) # 逆序建图
return self.topologicalSortingKahn(graph_dict)
|
思路 1：复杂度分析
#
- 时间复杂度：$O(n + m)$，其中 $n$ 是图中节点数目，$m$ 是图中边数目。
- 空间复杂度：$O(n + m)$。