0802. Find Eventual Safe States¶
题目信息¶
- 题号:
0802
- 难度:
Medium
- 主题:
有向图、终止状态、安全节点
- 原题:
- 重点:
从安全节点出发的每一条可能路径都必须最终停在终止节点;图可以含自环或其他有向环,结果按节点编号升序返回
题目重述¶
给定一个有 n 个节点的有向图,节点编号为 0 至 n - 1。邻接表 graph[i] 列出从节点 i 可以直接到达的所有节点。没有出边的节点称为终止节点。
若从某个节点出发,无论之后在每一步选择哪一条出边,最终都一定会到达终止节点,而不会无限停留在自环或其他有向环中,则该节点是最终安全节点。请返回全部最终安全节点的编号,并按升序排列。
1 <= n <= 10^4,图中边数在 [1, 4 * 10^4] 范围内;邻接点编号均合法,每个邻接表严格递增,图中可以存在自环和其他有向环。
自建示例¶
只有孤立的终止节点安全:
输入:graph = [[1],[2],[1],[]]
输出:[3]
解释:节点 1 与 2 构成有向环,节点 0 会进入该环,因此 0、1、2 都不安全;节点 3 没有出边,是终止节点。
所有路径都能终止:
输入:graph = [[1],[2],[],[1,2]]
输出:[0,1,2,3]
解释:节点 2 是终止节点,其余节点的每条路径最终也都会到达节点 2,因此全部节点安全。
自环节点不安全:
输入:graph = [[0],[]]
输出:[1]
解释:节点 0 有一条指向自身的边,从它出发可以永远停留在自环中,因此不安全;节点 1 没有出边,是安全的终止节点。