。找到最終的安全狀態

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) 來檢測循環並將節點分類為安全或不安全。

主要見解：

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

方法：

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

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

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

步驟：

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

讓我們用 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]
?>

解釋：

1. DFS 函數:

   • dfs 函數對節點執行深度優先搜索，當它啟動時將其標記為“訪問”(1)，當其所有鄰居都安全時將其標記為“安全”(2)。
   • 如果其任何鄰居導致循環（由 dfs($neighbor) == 1 表示），則該節點被標記為不安全 (1)。
   • 如果所有鄰居都通向終端節點或安全節點，則將其標記為安全（2）。

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]
?>

時間與空間複雜度：

• 時間複雜度：O(n e)，其中n是節點數，e
是邊數。我們訪問每個節點一次並處理每條邊一次。
• 空間複雜度：O(n)
用於存取的陣列和遞歸堆疊。

此解決方案使用 DFS 有效地確定安全節點，確保滿足問題限制。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫

一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。找到最終的安全狀態的詳細內容。更多資訊請關注PHP中文網其他相關文章！