Code & Func

第44天。

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

1
bool check(vector<vector<int>>& graph, vector<bool> &color, int i) {
2
    for(auto &j: graph[i]) {
3
        if (!color[j]) return false;
4
    }
5
    return true;
6
}
7
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
8
    int size = graph.size();
9
    vector<int> res;
10
    if (size == 0) return res;
11

12
    vector<bool> color(size, false);
13
    bool change = false;
14
    for(int i = 0;i < size; i++)
15
        if (graph[i].size() == 0) {
19 collapsed lines
16
            color[i] = true;
17
            change = true;
18
        }
19

20
    while(change) {
21
        change = false;
22
        for(int i = 0;i < size; i++) {
23
            if (color[i] == false && check(graph, color, i)) {
24
                color[i] = true;
25
                change = true;
26
            }
27
        }
28
    }
29

30
    for(int i = 0;i < size; i++) {
31
        if (color[i]) res.push_back(i);
32
    }
33
    return res;
34
}

后来发现好像可以用深度优先来做，主要的想法是，一个环中所有的节点都是不安全的，我们把不安全的节点都筛选出来，即可得到所有安全的节点。因此就把问题变成了找到图中所有在环中的节点。在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
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
2
    int size = graph.size();
3
    vector<int> res;
4
    if (size == 0) return res;
5

6
    vector<int> color(size, 0); // 0 mean unvisit
7
    for(int i = 0;i < size; i++) {
8
        if (color[i] == 0) dfs(graph, color, i);
9
    }
10

11
    for(int i = 0;i < size; i++) {
12
        if (color[i] == 2) res.push_back(i);
13
    }
14
    return res;
15

17 collapsed lines
16
}
17

18
int dfs(vector<vector<int>> &graph, vector<int> &color, int node) {
19
    // cout << "visit" << node << endl;
20
    color[node] = 1; // in dfs
21
    for(int j = 0;j < graph[node].size(); j++) {
22
        int i = graph[node][j];
23
        if ( (color[i] == 0 && dfs(graph, color, i) == 3) ||
24
            color[i] == 1 || color[i] == 3
25
            ) {
26
            color[node] = 3;
27
            return 3;
28
        }
29
    }
30
    color[node] = 2;// safe node
31
    return color[node];
32
}