難度：★★★★☆
類型：圖
方法：深度優(yōu)先搜索

力扣鏈接請移步本題傳送門
更多力扣中等題的解決方案請移步力扣中等題目錄

題目

在有向圖中, 我們從某個節(jié)點和每個轉(zhuǎn)向處開始, 沿著圖的有向邊走。 如果我們到達的節(jié)點是終點 (即它沒有連出的有向邊), 我們停止。

現(xiàn)在, 如果我們最后能走到終點，那么我們的起始節(jié)點是最終安全的。 更具體地說, 存在一個自然數(shù) K, 無論選擇從哪里開始行走, 我們走了不到 K 步后必能停止在一個終點。

哪些節(jié)點最終是安全的？ 結果返回一個有序的數(shù)組。

該有向圖有 N 個節(jié)點，標簽為 0, 1, ..., N-1, 其中 N 是 graph 的節(jié)點數(shù). 圖以以下的形式給出: graph[i] 是節(jié)點 j 的一個列表，滿足 (i, j) 是圖的一條有向邊。

示例：
輸入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
輸出：[2,4,5,6]
這里是上圖的示意圖。

提示：

graph 節(jié)點數(shù)不超過 10000.
圖的邊數(shù)不會超過 32000.
每個 graph[i] 被排序為不同的整數(shù)列表， 在區(qū)間 [0, graph.length - 1] 中選取。

解答

根據(jù)題目的要求，一個結點安全的前提條件是，從這個結點出發(fā)，不會墜入環(huán)形區(qū)域。因此，可以通過這個法則，對每個結點是否安全作出判斷。

圖的問題常常可以用深度優(yōu)先搜索來解決。定義深度優(yōu)先搜素函數(shù)dfs()，函數(shù)的輸入為圖中的某結點，函數(shù)的返回值為布爾值，表達了該結點是否是安全的。在函數(shù)內(nèi)部通過遞歸調(diào)用實現(xiàn)判斷。

定義一個輔助字典color，用來表達每個結點被染成的顏色，染色的目的在于尋找關聯(lián)區(qū)域，并判斷是否墜入環(huán)形循環(huán)。未被染色的結點定義為白色，判斷結果為安全的結點被染色成黑色，其他結點被染成灰色，表達遍歷過程中已經(jīng)遇到過。

在函數(shù)入口定義遞歸終點，即如果當前結點node已經(jīng)被染過色，如果這個顏色是灰色，說明這個回到了遇到過的位置，也就是說，墜入了環(huán)形區(qū)域，返回False，否則如果該結點是黑色，說明已經(jīng)判斷過該結點是安全的，返回True。

接下來是對沒有遇到過node結點的情況處理。首先把node染成灰色，表示已經(jīng)在這個結點留下了足跡，然后遍歷node結點的所有下一跳結點next_node，只要有任意一個下一跳結點不安全，那么這個結點也是不安全的，判斷next_node是否安全可以采用遞歸調(diào)用本函數(shù)的方式。

通過了所有下一跳結點的校驗，說明當前結點node是安全的，將這個安全的結點染色成黑色，并返回True即可。

我們使用過濾器來過濾出圖中所有安全的結點。

import collections


class Solution(object):
    def eventualSafeNodes(self, graph):
        white, gray, black = 0, 1, 2
        color = collections.defaultdict(int)

        def dfs(node):
            if color[node] != white:
                return color[node] == black

            color[node] = gray
            for next_node in graph[node]:
                if not dfs(next_node):
                    return False
            color[node] = black
            return True

        return list(filter(dfs, range(len(graph))))

如有疑問或建議，歡迎評論區(qū)留言~

有關更多力扣中等題的python解決方案，請移步力扣中等題解析