0802. Find Eventual Safe States

题目信息

题号:

0802

难度:

Medium

主题:

有向图、终止状态、安全节点

原题:

LeetCode 0802

重点:

从安全节点出发的每一条可能路径都必须最终停在终止节点;图可以含自环或其他有向环,结果按节点编号升序返回

题目重述

给定一个有 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 没有出边,是安全的终止节点。