[802. Find Eventual Safe States](https://leetcode.com/problems/find-eventual-safe-states/)

### 題目描述

There is a directed graph of `n` nodes with each node labeled from `0` to `n - 1`. The graph is represented by a **0-indexed** 2D integer array graph where `graph[i]` is an integer array of nodes adjacent to node `i`, meaning there is an edge from node `i` to each node in `graph[i]`.

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).

Return *an array containing all the **safe nodes** of the graph.* The answer should be sorted in **ascending** order.

### 範例

**Example 1:**


Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Explanation: The given graph is shown above.
Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them.
Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.

**Example 2:**

Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
Output: [4]
Explanation:
Only node 4 is a terminal node, and every path starting at node 4 leads to node 4.

**Constraints**:

* `n` == `graph.length`
* 1 <= `n` <= 10^4^
* 0 <= `graph[i].length` <= `n`
* 0 <= `graph[i][j]` <= n - 1
* `graph[i]` is sorted in a strictly increasing order.
* The graph may contain self-loops.
* The number of edges in the graph will be in the range [1, 4 * 10^4^].

### 解答
#### C++

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int numNodes = graph.size();
        vector<int> indegree(numNodes);
        vector<vector<int>> adj(numNodes);

        for (int nodeID = 0; nodeID < numNodes; nodeID ++) {
            for (int next : graph[nodeID]) {
                adj[next].push_back(nodeID);
                indegree[nodeID] ++;
            }
        }
        queue<int> frontier;
        for (int nodeID = 0; nodeID < numNodes; nodeID ++) {
            if (indegree[nodeID] == 0) {
                frontier.push(nodeID);
            }
        }
        vector<bool> safeNodes(numNodes);
        while (not frontier.empty()) {
            int u = frontier.front();
            frontier.pop();
            safeNodes[u] = true;
            for (const auto& next : adj[u]) {
                indegree[next] --;
                if (indegree[next] == 0) {
                    frontier.push(next);
                }
            }
        }
        vector<int> ans;
        for (int nodeID = 0; nodeID < numNodes; nodeID ++) {
            if (safeNodes[nodeID]) {
                ans.push_back(nodeID);
            }
        }
        return ans;
    }
};

> [name=Jerry Wu][time=12 Jul, 2023]

#### Python

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        cache = {}

        def dfs(node):
            if node in cache:
                return cache[node]
            cache[node] = False
            for child in graph[node]:
                if not dfs(child):
                    return False
            cache[node] = True
            return True

        ans = []
        for i in range(n):
            if dfs(i):
                ans.append(i)
        return ans

> [name=Yen-Chi Chen][time=Thu, Jul 13, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)