In a directed graph, we start at some node and every turn, walk along a directed edge of the graph. If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.

Now, say our starting node is *eventually safe *if and only if we must eventually walk to a terminal node. More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps.

Which nodes are eventually safe? Return them as an array in sorted order.

The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the length of graph. The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph.

1
2
3
4
Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Here is a diagram of the above graph.

Illustration of graph

Note:

  • graph will have length at most 10000.
  • The number of edges in the graph will not exceed 32000.
  • Each graph[i] will be a sorted list of different integers, chosen within the range [0, graph.length - 1].

这道题可以用找环来解决，所有在环中的node和后继node有在环中的node都不是safe的。使用DFS来搜索环，遇到已经判断过的就不需要再继续搜索。

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
class Solution {
    vector<int> circle;
    vector<int> visited;
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        circle.assign(graph.size(), 0);
        visited.assign(graph.size(), 0);
        unordered_set<int> path;
        for (int i = 0; i < graph.size(); i++) {
            dfs(graph, path, i);
        }
        vector<int> ans;
        for (int i = 0; i < circle.size(); i++) {
            if (!circle[i])
                ans.push_back(i);
        }
        return ans;
    }

    void dfs (vector<vector<int>>& graph, unordered_set<int> &path, int node) {
        if (visited[node]) {
            if (circle[node] || path.count(node)) {
                for (auto i : path) {
                    circle[i] = 1;
                }
            }
            return;
        }

        visited[node] = 1;
        path.insert(node);
        for (auto i : graph[node]) {
            dfs(graph, path, i);
        }
        path.erase(node);
    }

};