LeetCode 找到最终的安全状态题解

LeetCode 找到最终的安全状态题解题目描述给定一个有向图找到所有安全节点。安全节点是永远不会走向环的节点。示例输入graph [[1,2],[2,3],[5],[0],[5],[],[]]输出[2,4,5,6]解题思路方法拓扑排序思路使用拓扑排序找出所有入度为 0 的节点。删除这些节点并更新其邻居的入度。重复上述步骤直到没有入度为 0 的节点。剩余的节点都是安全节点。复杂度分析时间复杂度O(V E)。空间复杂度O(V E)。代码实现from collections import deque def eventual_safe_nodes(graph): n len(graph) indegree [0] * n reverse_graph [[] for _ in range(n)] for i in range(n): for j in graph[i]: reverse_graph[j].append(i) indegree[j] 1 queue deque([i for i in range(n) if indegree[i] 0]) safe [False] * n while queue: node queue.popleft() safe[node] True for neighbor in reverse_graph[node]: indegree[neighbor] - 1 if indegree[neighbor] 0: queue.append(neighbor) return [i for i in range(n) if safe[i]] # 测试 def test_eventual_safe_nodes(): graph [[1, 2], [2, 3], [5], [0], [5], [], []] print(eventual_safe_nodes(graph)) # 输出[2, 4, 5, 6] if __name__ __main__: test_eventual_safe_nodes()总结找到最终的安全状态是拓扑排序的典型应用通过删除入度为 0 的节点来找出安全节点。