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 的节点来找出安全节点。
