。找到最終的安全狀態-php教程-PHP中文網

802。找出最終的安全狀態

難度：中

主題：深度優先搜尋、廣度優先搜尋、圖表、拓樸排序

有一個由 n 個節點組成的有向圖，每個節點標記為從 0 到 n - 1。此圖由0 索引 2D 整數陣列圖表示，其中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 4
0
0
graph[i] 依嚴格升序排序。
圖表可能包含自循環。
圖中的邊數將在 [1, 4 * 10⁴] 範圍內。

解：

我們需要辨識圖中的所有安全節點。這涉及檢查是否從給定節點開始，每條路徑最終都會到達終端節點或另一個安全節點。此解決方案使用深度優先搜尋 (DFS) 來檢測循環並將節點分類為安全或不安全。

主要見解：

終端節點：沒有出邊的節點是終端節點。
安全節點：如果從該節點開始，所有路徑最終都通向終端節點或其他安全節點，則該節點是安全的。
循環檢測：如果一個節點是循環的一部分，那麼它不是一個安全節點，因為從它開始的路徑不會通向終端節點。

方法：

我們使用 DFS 來探索每個節點並確定它是否是循環的一部分。屬於循環的一部分或導致循環的節點被標記為不安全。
最終通向終端節點或其他安全節點的節點被標記為安全。

我們使用具有三種狀態的訪問數組：

0：該節點尚未被訪問過。
1：當前正在訪問該節點（即在遞歸堆棧中）。
2：節點已完全處理並且安全。

步驟：

對每個節點進行DFS。
使用訪問過的狀態來標記安全/不安全節點。
收集所有安全的節點。

讓我們用 PHP 實現這個解決方案：802。找到最終的安全狀態

<?php /**
 * @param Integer[][] $graph
 * @return Integer[]
 */
function eventualSafeNodes($graph) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * DFS helper function
 *
 * @param $node
 * @param $graph
 * @param $visited
 * @return int|mixed
 */
function dfs($node, $graph, &$visited) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$graph1 = [[1,2],[2,3],[5],[0],[5],[],[]];
$graph2 = [[1,2,3,4],[1,2],[3,4],[0,4],[]];

print_r(eventualSafeNodes($graph1)) . "\n"; // Output: [2,4,5,6]
print_r(eventualSafeNodes($graph2)) . "\n"; // Output: [4]
?>

登入後複製

解釋：

DFS 函數:
- dfs 函數對節點執行深度優先搜索，當它啟動時將其標記為“訪問”(1)，當其所有鄰居都安全時將其標記為“安全”(2)。
- 如果其任何鄰居導致循環（由 dfs($neighbor) == 1 表示），則該節點被標記為不安全 (1)。
- 如果所有鄰居都通向終端節點或安全節點，則將其標記為安全（2）。
主要功能：
- 我們迭代所有節點並使用DFS來檢查每個節點是否安全。
- 所有安全節點都收集在 $safeNodes 數組中並返回。

演練示例：

示例1：

$graph = [[1,2],[2,3],[5],[0],[5],[],[]];
print_r(eventualSafeNodes($graph));

登入後複製

在此示例中，節點 5 和 6 是終端節點（沒有傳出邊）。
節點4通向節點5，所以也是安全的。
節點2通向節點5，所以是安全的。
節點1和0最終會導致環路或者不安全節點，所以它們是不安全的。

輸出：

[2, 4, 5, 6]

登入後複製

示例2：

$graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]];
print_r(eventualSafeNodes($graph));

登入後複製

在本例中，只有節點 4 是終端節點，所有從節點 4 開始的路徑都通向節點 4。
所有其他節點最終都會導致循環或不安全節點。

輸出：

<?php /**
 * @param Integer[][] $graph
 * @return Integer[]
 */
function eventualSafeNodes($graph) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * DFS helper function
 *
 * @param $node
 * @param $graph
 * @param $visited
 * @return int|mixed
 */
function dfs($node, $graph, &$visited) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$graph1 = [[1,2],[2,3],[5],[0],[5],[],[]];
$graph2 = [[1,2,3,4],[1,2],[3,4],[0,4],[]];

print_r(eventualSafeNodes($graph1)) . "\n"; // Output: [2,4,5,6]
print_r(eventualSafeNodes($graph2)) . "\n"; // Output: [4]
?>

登入後複製