题目链接：find-eventual-safe-states
题目描述
在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。 如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。现在, 如果我们最后能走到终点，那么我们的起始节点是最终安全的。 更具体地说, 存在一个自然数 K, 无论选择从哪里开始行走, 我们走了不到 K 步后必能停止在一个终点。哪些节点最终是安全的？ 结果返回一个有序的数组。该有向图有 N 个节点，标签为 0, 1, …, N-1, 其中 N 是 graph 的节点数. 图以以下的形式给出: graph[i] 是节点 j 的一个列表，满足 (i, j) 是图的一条有向边。
题目分析
题目意思即找出非闭环的所有节点
- 我们可以从终点开始，即先找出那些没有出去的边的节点，即出度为0，这些节点一定符合条件，然后，反向搜索，找出他的上游，如果他的上游的所有出去的边都是在这些节点当中，则他的上游节点也是安全的。
- 我们还可以采用深搜的方式，对每个节点的所有出去的边进行搜索，如果他的所有下游节点都是安全的，则他也是安全的。
算法
反向边（Graph)
代码
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
| class Solution {
public List<Integer> eventualSafeNodes(int[][] G) {
List<Set<Integer>> graph = new ArrayList<>();
List<Set<Integer>> rgraph = new ArrayList<>();
Queue<Integer> queue = new LinkedList<>();
List<Integer> result = new ArrayList<>();
boolean[] safe = new boolean[G.length];
for (int i = 0; i < G.length; i++) {
graph.add(new HashSet<Integer>());
rgraph.add(new HashSet<Integer>());
}
for (int i = 0; i < G.length; i++) {
for (int j : G[i]) {
graph.get(i).add(j);
rgraph.get(j).add(i);
}
if (G[i].length == 0) queue.offer(i);
}
while (!queue.isEmpty()) {
int i = queue.poll();
safe[i] = true;
for (int j : rgraph.get(i)) {
graph.get(j).remove(i);
if (graph.get(j).isEmpty()) queue.offer(j);
}
}
for (int i = 0; i < G.length; i++) {
if (safe[i]) result.add(i);
}
return result;
}
}
|
深度优先搜索（Depth-first-Search）
代码
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
| import java.util.*;
class Solution {
enum Color {
WHITE,
BLACK,
GREY,
}
public List<Integer> eventualSafeNodes(int[][] graph) {
List<Integer> result = new ArrayList<>();
if (graph.length == 0) return result;
Color[] color = new Color[graph.length];
Arrays.fill(color, Color.WHITE);
for (int i = 0; i < graph.length; i++) {
if (dfs(graph, i, color)) result.add(i);
}
return result;
}
public boolean dfs(int[][] graph, int i, Color[] color) {
if (color[i] != Color.WHITE) return color[i] == Color.BLACK;
color[i] = Color.GREY;
for (int child : graph[i]) {
if (!dfs(graph, child, color)) return false;
}
color[i] = Color.BLACK;
return true;
}
}
|
