友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
802. 找到最终的安全状态
有一个有 n 个节点的有向图，节点按 0 到 n - 1 编号。图由一个 索引从 0 开始 的 2D 整数数组 graph`表示， `graph[i]`是与节点 `i 相邻的节点的整数数组，这意味着从节点 i 到 `graph[i]`中的每个节点都有一条边。
如果一个节点没有连出的有向边，则该节点是 终端节点。如果从该节点开始的所有可能路径都通向 终端节点 ，则该节点为 安全节点。
返回一个由图中所有 安全节点 组成的数组作为答案。答案数组中的元素应当按 升序 排列。
示例 1：
输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]] 输出：[2,4,5,6] 解释：示意图如上。 节点 5 和节点 6 是终端节点，因为它们都没有出边。 从节点 2、4、5 和 6 开始的所有路径都指向节点 5 或 6 。
示例 2：
输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]] 输出：[4] 解释: 只有节点 4 是终端节点，从节点 4 开始的所有路径都通向节点 4 。
提示：
-
n == graph.length -
1 <= n <= 104 -
0 <= graph[i].length <= n -
0 <= graph[i][j] <= n - 1 -
graph[i]按严格递增顺序排列。 -
图中可能包含自环。
-
图中边的数目在范围
[1, 4 * 10^4^]内。
思路分析
深度优先搜索，广度优先搜索或拓扑排序。
如果使用拓扑排序，需要构造反向图，然后从入度为 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
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-06-29 21:20:53
*/
public List<Integer> eventualSafeNodes(int[][] graph) {
int[][] reversed = new int[graph.length][];
for (int i = 0; i < graph.length; i++) {
int[] target = graph[i];
for (int t : target) {
if (Objects.isNull(reversed[t])) {
reversed[t] = new int[]{i};
} else {
int[] temp = new int[reversed[t].length + 1];
System.arraycopy(reversed[t], 0, temp, 0, reversed[t].length);
temp[temp.length - 1] = i;
reversed[t] = temp;
}
}
}
Set<Integer> result = new TreeSet<>();
for (int i = 0; i < reversed.length; i++) {
if (Objects.isNull(graph[i]) || graph[i].length == 0) { // 没有进边
dfs(graph, reversed, result, i);
}
}
return new ArrayList<>(result);
}
private void dfs(int[][] graph, int[][] reversed, Set<Integer> result, int index) {
if (result.contains(index)) {
return;
}
result.add(index);
int[] source = reversed[index];
if (Objects.isNull(source)) {
return;
}
for (int s : source) {
int[] targets = graph[s];
if (targets.length == 1) {
dfs(graph, reversed, result, s);
} else {
boolean flag = true;
for (int t : targets) {
if (!result.contains(t)) {
flag = false;
break;
}
}
if (flag) {
dfs(graph, reversed, result, s);
}
}
}
}