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 。
1
2
3
4
5

解法

这道题的本质究其根本就是寻找有无环路，如果一道题目需要检测图中是否存在环路，算法如下：

1. 深度优先搜索（DFS） ：通过深度优先搜索遍历图的所有节点，并标记节点状态，如果在搜索过程中发现某个节点已经被访问过且还未完成遍历，则存在环路。
2. 广度优先搜索（BFS） ：通过广度优先搜索遍历图的所有节点，并检测是否存在环路。
3. 拓扑排序：拓扑排序是一种特殊的排序算法，它可以对有向无环图进行排序，如果图中存在环路，则无法进行拓扑排序。
4. 并查集：并查集也可以用于检测图中是否存在环路，特别适用于无向图

BFS + 拓扑序列 + 逆转图

class Solution {
    int N = 100010, M = N * 2 + 10, idx = 0;
    int[] ne = new int[M], e = new int[M], h = new int[N], cnt = new int[N];
    public void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    public List<Integer> eventualSafeNodes(int[][] graph) {
        // 首先想到的是拓扑序列，因为终端节点意味着没有出度，
        // 能所有边都到达终端节点的即为安全节点，所以可以想逆转图，即出度和入度转换
        Arrays.fill(h, -1);
        int n = graph.length;
        for(int i = 0;i < n;i ++) {
            for(int j : graph[i]) {
                add(j, i); // 转换出度入度
                cnt[i] ++;
            }
        }
        Deque<Integer> de = new ArrayDeque<>();  // 注意这个双向队列
        for(int i = 0;i < n;i ++) {
            if(cnt[i] == 0) {
                de.addFirst(i);
            }
        }
        while(!de.isEmpty()) {
            int t = de.pollLast();
            for(int i = h[t];i != -1;i = ne[i]) {
                int j = e[i];
                cnt[j] --;
                if(cnt[j] == 0) {
                    de.addFirst(j);
                }
            }
        }
        ArrayList<Integer> ans = new ArrayList<>();
        for(int i = 0;i < n;i ++) {
            if(cnt[i] == 0) {
                ans.add(i);
            }
        }
        return ans;
    }
}
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

三色图

class Solution {
    // 三色标记法，0 --- 未被访问过， 1 --- 正在访问中， 2 --- 已经访问过
    public List<Integer> eventualSafeNodes(int[][] graph) {
       int n = graph.length; 
       int[] color = new int[n];
       List<Integer> ans = new ArrayList<Integer>();
       for(int i = 0;i < n;i ++) {
            if(isSafe(graph, color, i)) {
                ans.add(i);
            }
       }
       return ans;
    }
    public boolean isSafe(int[][] graph, int[] color, int x) {
        if(color[x] != 0) {
            return color[x] == 2;
        }
        color[x] = 1;
        for(int y : graph[x]) {
            if(!isSafe(graph, color, y)) {
                return false;
            }
        }
        color[x] = 2;
        return true;
    }
}
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