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

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

題目

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

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

哪些節(jié)點(diǎn)最終是安全的慨削？ 結(jié)果返回一個(gè)有序的數(shù)組友驮。

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

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

提示：

graph 節(jié)點(diǎn)數(shù)不超過 10000.
圖的邊數(shù)不會(huì)超過 32000.
每個(gè) graph[i] 被排序?yàn)椴煌恼麛?shù)列表哩治， 在區(qū)間 [0, graph.length - 1] 中選取。

解答

根據(jù)題目的要求衬鱼，一個(gè)結(jié)點(diǎn)安全的前提條件是业筏，從這個(gè)結(jié)點(diǎn)出發(fā)，不會(huì)墜入環(huán)形區(qū)域鸟赫。因此蒜胖，可以通過這個(gè)法則消别，對(duì)每個(gè)結(jié)點(diǎn)是否安全作出判斷。

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

定義一個(gè)輔助字典color纠亚，用來表達(dá)每個(gè)結(jié)點(diǎn)被染成的顏色，染色的目的在于尋找關(guān)聯(lián)區(qū)域筋夏，并判斷是否墜入環(huán)形循環(huán)蒂胞。未被染色的結(jié)點(diǎn)定義為白色，判斷結(jié)果為安全的結(jié)點(diǎn)被染色成黑色条篷，其他結(jié)點(diǎn)被染成灰色骗随，表達(dá)遍歷過程中已經(jīng)遇到過。

在函數(shù)入口定義遞歸終點(diǎn)赴叹，即如果當(dāng)前結(jié)點(diǎn)node已經(jīng)被染過色鸿染，如果這個(gè)顏色是灰色，說明這個(gè)回到了遇到過的位置乞巧，也就是說牡昆，墜入了環(huán)形區(qū)域，返回False摊欠，否則如果該結(jié)點(diǎn)是黑色，說明已經(jīng)判斷過該結(jié)點(diǎn)是安全的柱宦，返回True些椒。

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

通過了所有下一跳結(jié)點(diǎn)的校驗(yàn)蚓炬，說明當(dāng)前結(jié)點(diǎn)node是安全的松逊，將這個(gè)安全的結(jié)點(diǎn)染色成黑色，并返回True即可肯夏。

我們使用過濾器來過濾出圖中所有安全的結(jié)點(diǎn)经宏。

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))))

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

有關(guān)更多力扣中等題的python解決方案，請(qǐng)移步力扣中等題解析