leetcode：802. 找到最终的安全状态【反图 + 入度统计 + deque + 找出图中非环的节点】

分析

这道题找的是终端节点和安全节点，显然这些节点必定不在环中
我们构造它的反图（全部边反向），入度为0的就是终端节点
然后我们维护一个deque放终端节点和安全节点
每遍历一个节点就是清理这个节点，就将反图的下一个节点的入度减1
如果下一个节点的入度减到0，那么它就是安全的了

ac code

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:  
        # 反图 + 入度为0(过程减少)  
        # 在给定的图中，找出非环的节点   
        n = len(graph)
        rg = defaultdict(list)
        for i in range(n):
            for next in graph[i]:
                rg[next].append(i)
        
        inDegree = [0] * n
        for a in rg:
            for b in rg[a]:
                inDegree[b] += 1

        # 先放入度为0的终端节点
        dq = deque([i for i, d in enumerate(inDegree) if d == 0])
        # 找出安全节点
        while dq:
            for x in rg[dq.popleft()]:
                inDegree[x] -= 1
                if inDegree[x] == 0:
                    dq.append(x)

        return [i for i, d in enumerate(inDegree) if d == 0] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

总结

等价为找非环节点，考虑反图和入度
找到终端节点使用deque，依次减掉入度，最终得到剩下的安全节点