C/C++教程

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

本文主要是介绍[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;
    }
};
这篇关于[LeetCode 802.] 找到最终的安全状态的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!