Leetcode 802. 找到最终的安全状态（DFS + 记忆化搜索）

有一个有 n 个节点的有向图，节点按 0 到 n - 1 编号。图由一个 索引从 0 开始 的 2D 整数数组 graph表示， graph[i]是与节点 i 相邻的节点的整数数组，这意味着从节点 i 到 graph[i]中的每个节点都有一条边。

如果一个节点没有连出的有向边，则它是 终端节点 。如果没有出边，则节点为终端节点。如果从该节点开始的所有可能路径都通向 终端节点 ，则该节点为 安全节点 。

返回一个由图中所有 安全节点 组成的数组作为答案。答案数组中的元素应当按 升序 排列。

---

输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出：[2,4,5,6]
解释：示意图如上。
节点 5 和节点 6 是终端节点，因为它们都没有出边。
从节点 2、4、5 和 6 开始的所有路径都指向节点 5 或 6 。

---

【思路】：
A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).

判断一个节点是否是安全节点：1、如果其出度是终端节点，没问题。2、如果其出度是另一个安全节点，也没问题。

这里就明显有一个递归。

记得优化！采用记忆化搜索的方式，用一个hash存储搜出来的安全节点，下次就不用再搜了。

---

【代码】：

/**
 * @param {number[][]} graph
 * @return {number[]}
 */
//判断某节点下所有出度是否都能到。因为要求所有可能的路径都要到
//return boolean
var isSafeNode = function(node, graph, zhongduan, vis, hash){
    if(hash.get(node) != undefined) return true;
    if(zhongduan.indexOf(node) != -1)   return true;
    let canAri = true;
    let chudu = graph[node];
    vis[node] = 1;
    for(let i = 0;i < chudu.length;i++){
        //如果出现环状，那么肯定就不是安全节点，比如示例1中的0，1，3构成环。
        if(vis[chudu[i]] == 1)  {
            canAri = false;break;
        }
        if(!isSafeNode(chudu[i], graph, zhongduan, vis, hash)){
            canAri = false;break;
        }
    } 
    //设置一个缓存
    if(canAri) hash.set(node, 1);
    vis[node] = 0;
    return canAri;
}

var eventualSafeNodes = function(graph) {
    var res = [];
    var hash = new Map();       //记录所有的安全节点
    var zhongduan = [];
    var vis = new Array(graph.length).fill(0);
    for(let i =0 ;i < graph.length;i++){
        let  chudu = graph[i];
        if(chudu.length == 0) {
            zhongduan.push(i);
            hash.set(i, 1);
        }        //没有出度的终端节点
        
        //如果i节点下面的所有子节点都可以到
        if(isSafeNode(i, graph, zhongduan, vis, hash)){
            res.push(i);    
        }
    }
    return res;
};
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