0802. 找到最终的安全状态

0802. 找到最终的安全状态 #

  • 标签:深度优先搜索、广度优先搜索、图、拓扑排序
  • 难度:中等

题目大意 #

给定一个有向图 graph,其中 graph[i] 是编号 j 节点的一个列表,满足 (i, j) 是图的一条有向边。

要求:找出图中所有安全的起始节点,将其存入数组作为答案返回。

  • 安全的起始节点:从该节点出发,无论每一步选择沿哪条有向边行走,最后必然再有限步内到达终点,则该起始节点称为安全的起始节点。

解题思路 #

根据题意可知,安全的起始节点所对应的终点,一定是出度为 0 的节点。而安全节点一定能在有限步内到达终点,则说明安全节点一定不在「环」内。

我们可以利用拓扑排序来判断顶点是否在环中。为了找出起始节点,可以采取逆序建图的方式,将所有边进行反向。这样出度为 0 的终点就变为了入度为 0 的点。在通过拓扑排序不断移除入度为 0 的点之后,如果不在「环」中的点,最后入度一定为 0,这些点也就是安全的起始节点。而在「环」中的点,最后入度一定不为 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
26
27
28
29
30
import collections

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        size = len(graph)
        indegrees = [0 for _ in range(size)]
        edges = collections.defaultdict(list)

        for i in range(len(graph)):
            for node in graph[i]:
                x, y = i, node
                edges[y].append(x)
                indegrees[x] += 1
        queue = collections.deque([])
        for i in range(size):
            if not indegrees[i]:
                queue.append(i)

        while queue:
            y = queue.popleft()
            for x in edges[y]:
                indegrees[x] -= 1
                if not indegrees[x]:
                    queue.append(x)

        res = []
        for i in range(size):
            if not indegrees[i]:
                res.append(i)
        return res
本站总访问量  次  |  您是本站第  位访问者