完整题目描述

题目名称： 找到最终的安全状态

问题描述：

在一个由n个节点组成的图中，每个节点代表一个城市，节点之间的边表示城市之间的直接连接路径。这些连接路径上可能存在危险，使得某些路径在特定时间后变得不安全。每个节点（城市）都有一个固定的安全时间s[i]，表示如果到达该节点的时间小于或等于s[i]，则该节点被认为是安全的；否则，该节点被认为是危险的。

给定图的邻接表表示graph，其中graph[i]包含与节点i直接相连的所有节点（不包括i自身）。同时，给定每个节点的安全时间数组s。你需要找到一种方式，从节点0（起始节点）开始遍历图，使得在遍历过程中，所有经过的节点都保持安全状态（即到达时间小于等于其安全时间）。

要求：

• 返回从节点0开始的一种可能的遍历顺序，使得所有节点在遍历过程中都保持安全。
• 如果不存在这样的遍历顺序，则返回空数组或特定标识（如-1）。

注意：

• 图的节点数n在1到10^5之间。
• 每个节点的安全时间s[i]是一个非负整数，不超过10^9。
• 图的表示方法可能包括自环，但不存在重边。

示例

输入：

graph = [[1, 2], [2], [3], []]
s = [2, 4, 3, 0]

输出：

[0, 1, 2, 3]

解释：

• 从节点0开始，安全时间为2。
• 遍历到节点1，此时时间为1（从0到1的步数），节点1的安全时间为2，因此是安全的。
• 然后从节点1遍历到节点2，此时时间为2（从0到1再到2的步数），节点2的安全时间为4，因此也是安全的。
• 最后从节点2遍历到节点3，此时时间为3（从0到1再到2最后到3的步数），节点3的安全时间为3，仍然是安全的。

PHP 示例代码

function eventualSafeNodes($graph, $s) {
    $n = count($graph);
    $visited = array_fill(0, $n, 0); // 0: 未访问, 1: 安全, -1: 不安全
    $result = [];

    function dfs($node, $time, &$graph, &$s, &$visited, &$result) {
        if ($visited[$node] != 0) {
            return $visited[$node] == 1; // 如果已访问过，直接返回安全状态
        }

        $visited[$node] = -1; // 标记为正在访问中，暂时视为不安全
        $safe = true;

        foreach ($graph[$node] as $neighbor) {
            if (!dfs($neighbor, $time + 1, $graph, $s, $visited, $result)) {
                $safe = false;
            }
        }

        if ($safe && $time <= $s[$node]) {
            $visited[$node] = 1; // 标记为安全
            $result[] = $node;
        }

        return $safe;
    }

    if (dfs(0, 0, $graph, $s, $visited, $result)) {
        return $result;
    }

    return [];
}

// 示例使用
$graph = [[1, 2], [2], [3], []];
$s = [2, 4, 3, 0];
$result = eventualSafeNodes($graph, $s);
print_r($result);

Python 示例代码

def eventualSafeNodes(graph, s):
    n = len(graph)
    visited = [0] * n  # 0: 未访问, 1: 安全, -1: 不安全
    result = []

    def dfs(node, time):
        nonlocal visited, result
        if visited[node] != 0:
            return visited[node] == 1

        visited[node] = -1
        safe = True

        for neighbor in graph[node]:
            if not dfs(neighbor, time + 1):
                safe = False

        if safe and time <= s[node]:
            visited[node] = 1
            result.append(node)

        return safe

    if dfs(0, 0):
        return result
    return []

# 示例使用
graph = [[1, 2], [2], [3], []]
s = [2, 4, 3, 0]
result = eventualSafeNodes(graph, s)
print(result)

JavaScript 示例代码

function eventualSafeNodes(graph, s) {
    const n = graph.length;
    const visited = new Array(n).fill(0); // 0: 未访问, 1: 安全, -1: 不安全
    const result = [];

    function dfs(node, time) {
        if (visited[node] !== 0) {
            return visited[node] === 1;
        }

        visited[node] = -1;
        let safe = true;

        for (const neighbor of graph[node]) {
            if (!dfs(neighbor, time + 1)) {
                safe = false;
            }
        }

        if (safe && time <= s[node]) {
            visited[node] = 1;
            result.push(node);
        }

        return safe;
    }

    if (dfs(0, 0)) {
        return result;
    }
    return [];
}

// 示例使用
const graph = [[1, 2], [2], [3], []];
const s = [2, 4, 3, 0];
const result = eventualSafeNodes(graph, s);
console.log(result);

码小课网站中有更多关于图论、深度优先搜索（DFS）以及算法设计的相关内容分享给大家学习。