802. 找到最终的安全状态

🟠   🔖  深度优先搜索 广度优先搜索 图 拓扑排序  🔗 力扣 LeetCode

题目

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).

Return an array containing all thesafe nodes of the graph. The answer should be sorted in ascending order.

Example 1:

Illustration of graph

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]

Output: [2,4,5,6]

Explanation: The given graph is shown above.

Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them.

Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.

Example 2:

Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]

Output: [4]

Explanation:

Only node 4 is a terminal node, and every path starting at node 4 leads to node 4.

Constraints:

• n == graph.length
• 1 <= n <= 10^4
• 0 <= graph[i].length <= n
• 0 <= graph[i][j] <= n - 1
• graph[i] is sorted in a strictly increasing order.
• The graph may contain self-loops.
• The number of edges in the graph will be in the range [1, 4 * 104].

题目大意

有一个有 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.length
• 1 <= n <= 10^4
• 0 <= graph[i].length <= n
• 0 <= graph[i][j] <= n - 1
• graph[i] 按严格递增顺序排列。
• 图中可能包含自环。
• 图中边的数目在范围 [1, 4 * 104] 内。

解题思路

题目要求找出所有 最终安全的节点。如果从某节点出发，不会进入任何环，则该节点为最终安全节点。因此，任务可以归结为图中 判断哪些节点不在环内。

可以采用 深度优先搜索（DFS） 来检测环：

1. 辅助数组：
   • visited[i]: 标记节点 i 是否已被访问过。
   • inStack[i]: 标记节点 i 是否在当前递归栈中。
2. DFS 检测环：
   • 遍历图中所有节点，调用 hasCycle 检测是否有环。
   • 如果当前节点已在递归栈中（inStack[node] == true），说明存在环，返回 true。
   • 如果当前节点已经访问过（visited[node] == true），直接返回 false，说明该节点无环。
   • 对当前节点的邻居递归检查，若任何邻居存在环，则当前节点也在环内。
   • 如果当前节点没有形成环，从递归栈中移除（inStack[node] = false）。
3. 找出安全节点：
   • 遍历 inStack 数组，找到所有不在环中的节点。
   • 安全节点是那些最终 inStack[node] == false 的节点。
4. 返回结果：
   • 输出所有安全节点的索引。

复杂度分析

• 时间复杂度： O(V + E)，其中 V 是节点数，E 是边数，每个节点和边最多访问一次。
• 空间复杂度： O(V)，主要是辅助数组 visited 和 inStack 以及递归栈的开销。

代码

/**
 * @param {number[][]} graph
 * @return {number[]}
 */
var eventualSafeNodes = function (graph) {
	const n = graph.length;
	const visited = new Array(n).fill(false); // 标记节点是否访问过
	const inStack = new Array(n).fill(false); // 标记节点是否在递归栈中

	// 检测是否存在环
	const hasCycle = (node) => {
		if (inStack[node]) return true; // 当前节点在递归栈中，说明形成环
		if (visited[node]) return false; // 已访问且无环
		visited[node] = true; // 标记已访问
		inStack[node] = true; // 将当前节点加入递归栈
		for (let neighbor of graph[node]) {
			if (hasCycle(neighbor)) {
				return true; // 发现环
			}
		}
		inStack[node] = false; // 当前节点出栈
		return false; // 无环
	};

	// 遍历所有节点，检查环
	for (let i = 0; i < n; i++) {
		hasCycle(i);
	}

	// 找出最终安全的节点
	const safeNodes = [];
	for (let i = 0; i < n; i++) {
		if (!inStack[i]) {
			safeNodes.push(i); // 不在环中的节点是安全节点
		}
	}

	return safeNodes;
};

相关题目

题号	标题	题解	标签	难度	力扣
2392	给定条件下构造矩阵		图 拓扑排序 数组 1+	🔴	🀄️ 🔗