[数据结构与算法]【leetcode】802. 找到最终的安全状态（find-eventual-safe-states）（拓扑排序）[中等]

链接

https://leetcode-cn.com/problems/find-eventual-safe-states/

耗时

解题：23 min
题解：23 min

题意

在有向图中，以某个节点为起始节点，从该点出发，每一步沿着图中的一条有向边行走。如果到达的节点是终点（即它没有连出的有向边），则停止。

对于一个起始节点，如果从该节点出发，无论每一步选择沿哪条有向边行走，最后必然在有限步内到达终点，则将该起始节点称作是 安全 的。

返回一个由图中所有安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。

该有向图有 n 个节点，按 0 到 n - 1 编号，其中 n 是?graph?的节点数。图以下述形式给出：graph[i] 是编号 j 节点的一个列表，满足 (i, j) 是图的一条有向边。

?

示例 1：

输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出：[2,4,5,6]
解释：示意图如上。

示例 2：

输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
输出：[4]

?

提示：

• n == graph.length
• 1 <= n <= 104
• 0 <= graph[i].length <= n
• graph[i] 按严格递增顺序排列。
• 图中可能包含自环。
• 图中边的数目在范围 [1, 4 * 104] 内。

思路

根据题意，入度为 0 的终点肯定是安全的，那么只连接终点的节点也是安全的，只连接 只连接终点的节点 的节点也是安全的。那么思路就有了，入度为 0 的节点是答案，删除入度为 0 的节点之后，入度变为 0 的节点也是答案，以此类推。但是入度为 0 不好做，太慢，把入度变为出度就是拓扑排序。所以首先反转边，然后拓扑排序即可。

时间复杂度：$O(n+m)$

AC代码

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> in(n, 0);
        vector<vector<int>> graph_rev(n);
        for(int i = 0; i < n; ++i) {
            for(auto x : graph[i]) {
                graph_rev[x].push_back(i);
                in[i]++;
            }
        }
        
        queue<int> q;
        for(int i = 0; i <n; ++i) {
            if(in[i] == 0) {
                q.push(i);
            }
        }
        vector<int> ans;
        while(!q.empty()) {
            int now = q.front();
            q.pop();
            ans.push_back(now);
            for(auto to : graph_rev[now]) {
                in[to]--;
                if(in[to] == 0) q.push(to);
            }
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};