802. 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⁴
• 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⁴].

解答

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;
    }
};

Jerry Wu12 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

Yen-Chi ChenThu, Jul 13, 2023

Reference

回到題目列表