LeetCode 题解工作台
找到最终的安全状态
有一个有 n 个节点的有向图，节点按 0 到 n - 1 编号。图由一个 索引从 0 开始 的 2D 整数数组 graph 表示， graph[i] 是与节点 i 相邻的节点的整数数组，这意味着从节点 i 到 graph[i] 中的每个节点都有一条边。 如果一个节点没有连出的有向边，则该节点是 终端…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
出度为零的点是安全的，如果一个点只能到达安全的点，那么它同样是安全的，所以问题转换成了拓扑排序。 我们可以将图中所有边反向，得到一个反图，然后在反图上运行拓扑排序。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
有一个有 n 个节点的有向图，节点按 0 到 n - 1 编号。图由一个 索引从 0 开始 的 2D 整数数组 graph表示， graph[i]是与节点 i 相邻的节点的整数数组，这意味着从节点 i 到 graph[i]中的每个节点都有一条边。
如果一个节点没有连出的有向边，则该节点是 终端节点 。如果从该节点开始的所有可能路径都通向 终端节点（或另一个安全节点），则该节点为 安全节点。
返回一个由图中所有 安全节点 组成的数组作为答案。答案数组中的元素应当按 升序 排列。
示例 1：
输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]] 输出：[2,4,5,6] 解释：示意图如上。 节点 5 和节点 6 是终端节点，因为它们都没有出边。 从节点 2、4、5 和 6 开始的所有路径都指向节点 5 或 6 。
示例 2：
输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]] 输出：[4] 解释: 只有节点 4 是终端节点，从节点 4 开始的所有路径都通向节点 4 。
提示：
n == graph.length1 <= n <= 1040 <= graph[i].length <= n0 <= graph[i][j] <= n - 1graph[i]按严格递增顺序排列。- 图中可能包含自环。
- 图中边的数目在范围
[1, 4 * 104]内。
解题思路
方法一：拓扑排序
出度为零的点是安全的，如果一个点只能到达安全的点，那么它同样是安全的，所以问题转换成了拓扑排序。
我们可以将图中所有边反向，得到一个反图，然后在反图上运行拓扑排序。
时间复杂度 ，其中 表示图中的点数， 表示图中的边数。
class Solution:
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
rg = defaultdict(list)
indeg = [0] * len(graph)
for i, vs in enumerate(graph):
for j in vs:
rg[j].append(i)
indeg[i] = len(vs)
q = deque([i for i, v in enumerate(indeg) if v == 0])
while q:
i = q.popleft()
for j in rg[i]:
indeg[j] -= 1
if indeg[j] == 0:
q.append(j)
return [i for i, v in enumerate(indeg) if v == 0]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(m + n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Look for the candidate's understanding of graph traversal techniques like DFS and BFS.
- question_mark
Check if the candidate can implement topological sorting or manage indegree calculations effectively.
- question_mark
Ensure that the candidate can handle graph cycles and efficiently determine safe nodes.
常见陷阱
外企场景- error
Failing to correctly identify cycles, leading to incorrect results for non-terminal nodes.
- error
Not updating node states correctly during the DFS, resulting in missing safe nodes.
- error
Inaccurate handling of nodes with self-loops, which may cause confusion during graph traversal.
进阶变体
外企场景- arrow_right_alt
Adapt the problem to handle graphs with a larger number of nodes or edges.
- arrow_right_alt
Extend the problem to detect multiple types of cycles, not just those involving terminal nodes.
- arrow_right_alt
Modify the graph to allow for weighted edges, which would impact the safety of nodes.