[LeetCode 802.] 找到最终的安全状态

LeetCode 802. 找到最终的安全状态

题目描述

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

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

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

该有向图有 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] 内。

解题思路

题目要找的是必然能够走到最后无路可走的点，那我们反过来考察什么样的点可能永远走不到无路可走？当然是在环路上的点才可能一直绕圈永不停止。
我们可以用一种“删点”的方式来找出不在任何环上的点：先找出所有的终点，然后把指向他们的边删掉；重复操作，直到所有点和边都无法更新。
实际上这一过程，就是拓扑排序，只不过箭头指向反了过来而已。

参考代码

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        // 有环就不安全，把所有环上所有点去掉，留下DAG上的点就是了
        size_t n = graph.size();
        queue<int> q;
        vector<int> outDeg(n);
        vector<vector<int>> rg(n);
        for (size_t i = 0; i < n; i++) {
            auto&& v = graph[i];
            outDeg[i] = v.size();
            if (outDeg[i] == 0) {
                q.push(i);
            }
            for (int x : v) {
                rg[x].push_back(i);
            }
        }

        vector<int> res;
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            if (outDeg[x] != 0) continue;
            res.push_back(x);
            for (int y : rg[x]) {
                outDeg[y]--;
                if (outDeg[y] == 0) q.push(y);
            }
        }
        sort(res.begin(), res.end());
        return res;
    }
};