当前位置： 面试刷题>> 找到最终的安全状态 (经典算法题500道)
### 完整题目描述
**题目名称**： 找到最终的安全状态
**问题描述**：
在一个由`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 示例代码
```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 示例代码
```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 示例代码
```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）以及算法设计的相关内容分享给大家学习。