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

题目描述

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

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

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

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

数据范围

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

样例

输入样例1：

graph = [[1,2],[2,3],[5],[0],[5],[],[]]

输出样例1：

[2,4,5,6]

样例1解释：

输入样例2：

graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]

输出样例2：

[4]

题意

找到所有安全点，编号从小到大输出。

安全点：从某个点出发，无论如何都走不到环里，这个点称为安全点。

思路

性质

一个点，如果出度为0，这个点必然安全。

一个点，如果它所有出边对应的点都是安全的，那么，它也是安全的。

可以找到所有出度为0的点，将他们都删掉，然后，继续找到出度为0的点。直到不能删为止。

将所有边反向后，就是拓扑排序的过程了。

代码

C++

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> d(n);
        vector<vector<int>> g(n);
        // 建立反向图
        for ( int i = 0; i < n; i++ )
            for ( auto b : graph[i] )
            {
                // 原来是i -> b的，反向后就是从b -> i
                g[b].push_back(i);
                // 入度+1
                d[i]++;
            }

        // 找到所有入度为0的点
        queue<int> q;
        for ( int i = 0; i < n; i++ )
            if ( !d[i] ) q.push(i);
        
        while ( q.size() )
        {
            int t = q.front(); q.pop();
            for ( auto i : g[t] )
                // 删除t -> i这条边
                if ( --d[i] == 0 ) q.push(i);
        }

        // 找到所有安全的点，就是入度为0的点
        vector<int> res;
        for ( int i = 0; i < n; i++ )
            if ( !d[i] ) res.push_back(i);
        return res;
    }
};