Find Eventual Safe States

LeetCode

第44天。

今天的题目是Find Eventual Safe States:

最开始的想法是，从安全的节点开始在图中进行扩散，当一个节点所有边都指向一个安全的节点时，那它也是一个安全的节点，但是这样复杂度挺高的，所以虽然能过：

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
bool check(vector<vector<int>>& graph, vector<bool> &color, int i) {
    for(auto &j: graph[i]) {
        if (!color[j]) return false;
    }
    return true;
}
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
    int size = graph.size();
    vector<int> res;
    if (size == 0) return res;
    
    vector<bool> color(size, false);
    bool change = false;
    for(int i = 0;i < size; i++) 
        if (graph[i].size() == 0) {
            color[i] = true;
            change = true;
        }
    
    while(change) {
        change = false;
        for(int i = 0;i < size; i++) {
            if (color[i] == false && check(graph, color, i)) {
                color[i] = true;
                change = true;
            }
        }
    }
    
    for(int i = 0;i < size; i++) {
        if (color[i]) res.push_back(i);
    }
    return res;
}

后来发现好像可以用深度优先来做，主要的想法是，一个环中所有的节点都是不安全的，我们把不安全的节点都筛选出来，即可得到所有安全的节点。
因此就把问题变成了找到图中所有在环中的节点。在DFS时，维护一个状态，这个状态可能为：

  • 0：未访问（初始状态）
  • 1：访问中
  • 2：访问完成（安全状态）
  • 3：在环中（不安全状态）

先把所有节点的状态都初始化为0,当对第 i 个节点调用 dfs 时，则将其转换为1,然后遍历该节点所有能走的边，
如果下一个节点的状态为0，则对其调用dfs，如果下一个节点的状态为1或2，则该节点出现在环中，将状态转换为3，并直接返回为3。
当 i 节点对 j 节点调用 dfs 后，返回值如果为3的话，则 i 节点状态也变为 3, 并直接返回3。

如果第 i 个节点对所有路径都调用了 dfs 后，没有遇到返回值为 3 的情况，则该节点为安全的，所以将其状态转换为 2。

代码如下：

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
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
    int size = graph.size();
    vector<int> res;
    if (size == 0) return res;
    
    vector<int> color(size, 0); // 0 mean unvisit
    for(int i = 0;i < size; i++) {
        if (color[i] == 0) dfs(graph, color, i);
    }
    
    for(int i = 0;i < size; i++) {
        if (color[i] == 2) res.push_back(i);
    }
    return res;
    
}

int dfs(vector<vector<int>> &graph, vector<int> &color, int node) {
    // cout << "visit" << node << endl;
    color[node] = 1; // in dfs
    for(int j = 0;j < graph[node].size(); j++) {
        int i = graph[node][j];
        if ( (color[i] == 0 && dfs(graph, color, i) == 3) ||
            color[i] == 1 || color[i] == 3
            ) {
            color[node] = 3;
            return 3;
        }
    }
    color[node] = 2;// safe node
    return color[node];
}