LeetCode-找到最终的安全状态

yfx

August 6, 2021

533 views

No comments

1864 words

算法 C/C++ Python

<div class="tip share">请注意，本文编写于 1388 天前，最后修改于 1375 天前，其中某些信息可能已经过时。</div>

# Problem - [找到最终的安全状态](https://leetcode-cn.com/problems/find-eventual-safe-states/)

> **分析：**
>
> 根据题意可知，**若一个点的出度为0或其指向的所有结点为安全结点那么它就是安全结点**。这容易让我们联想到拓扑排序，但拓扑排序的思想是找入度为0的点，故我们可以把图内的所有变的指向逆向操作，则原题变为**若一个点的入度为0或其指向的所有结点为安全结点那么它就是安全结点**。则此时利用拓扑排序的思想便可以筛选出所有的安全结点，在一次拓扑排序之和，入度为0的点则为安全结点。
>
> **算法：**
>
> 拓扑排序

## 方法一：DFS

### 参考代码：

<div class="tab-container post_tab box-shadow-wrap-lg">
<ul class="nav no-padder b-b scroll-hide" role="tablist">
<li class='nav-item active' role="presentation"><a class='nav-link active' style="" data-toggle="tab" 
aria-controls='tabs-eefa6d03a70a52e56d804bd252552ede750' role="tab" data-target='#tabs-eefa6d03a70a52e56d804bd252552ede750'>**C++**</a></li><li class='nav-item ' role="presentation"><a class='nav-link ' style="" data-toggle="tab" 
aria-controls='tabs-fb4b3f26a3cc44bfb859e60b3eedb6e2291' role="tab" data-target='#tabs-fb4b3f26a3cc44bfb859e60b3eedb6e2291'>**Python 3**</a></li>
</ul>
<div class="tab-content no-border">
<div role="tabpanel" id='tabs-eefa6d03a70a52e56d804bd252552ede750' class="tab-pane fade active in">

```cpp
class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<int>> rgraph(n);
        vector<int> InDegree(n);
        for (int i = 0; i < n; ++ i) {
            for (int x : graph[i])
                rgraph[x].push_back(i);
            InDegree[i] = graph[i].size();
        }
        queue<int> q;
        for (int i = 0; i < n; ++ i)
            if (!InDegree[i]) q.push(i);
        while (q.size()) {
            int t = q.front(); q.pop();
            for (int x : rgraph[t]) {
                -- InDegree[x];
                if (!InDegree[x]) q.push(x);
            }
        }
        vector<int> ans;
        for (int i = 0; i < n; ++ i)
            if (!InDegree[i]) ans.push_back(i);
        return ans;
    }
};
```

</div><div role="tabpanel" id='tabs-fb4b3f26a3cc44bfb859e60b3eedb6e2291' class="tab-pane fade  ">

```python
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        rg = [[] for _ in graph]
        for i, g in enumerate(graph):
            for t in g:
                rg[t].append(i)
        InDegree = [len(g) for g in graph]
        q = deque([i for i, d in enumerate(InDegree) if d == 0])
        while q:
            for x in rg[q.popleft()]:
                InDegree[x] -= 1
                if InDegree[x] == 0: q.append(x)
        ans = [i for i, d in enumerate(InDegree) if d == 0]
        return ans
```

</div>
</div>
</div>

### 复杂度分析：

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

Last modification：August 18, 2021