802. 找到最终的安全状态

在有向图中，以某个节点为起始节点，从该点出发，每一步沿着图中的一条有向边行走。如果到达的节点是终点（即它没有连出的有向边），则停止。

对于一个起始节点，如果从该节点出发，无论每一步选择沿哪条有向边行走，最后必然在有限步内到达终点，则将该起始节点称作是 安全 的。

返回一个由图中所有安全的起始节点组成的数组作为答案。答案数组中的元素应当按 升序 排列。

该有向图有 n 个节点，按 0 到 n - 1 编号，其中 n 是 graph 的节点数。图以下述形式给出：graph[i] 是编号 j 节点的一个列表，满足 (i, j) 是图的一条有向边。

示例 1：

输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出：[2,4,5,6]
解释：示意图如上。

示例 2：

输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
输出：[4]

提示：

• n == graph.length
• 1 <= n <= 104
• 0 <= graph[i].length <= n
• graph[i] 按严格递增顺序排列。
• 图中可能包含自环。
• 图中边的数目在范围 [1, 4 * 104] 内。

DFS BFS 中等

代码

1. DFS

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        color = [0] * n
        def dfs(i)->bool:
            if color[i] > 0:
                return color[i] == 2
            color[i] = 1
            for nei in graph[i]:
                if not dfs(nei):
                    return False
            color[i] = 2
            return True            
        return [i for i in range(n) if dfs(i)]

2. 拓扑排序

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        iG = [ [] for _ in range(n) ] # 反向图
        ic = [0] * n # 图的入度图
        for s, es in enumerate(graph): # start, end
            for e in es:
                iG[e].append(s)
                # ic[e] += 1
            ic[s] = len(es)
        q = deque([i for i, n in enumerate(ic) if n == 0])
        while q:
            cur = q.popleft()
            for nei in iG[cur]:
                ic[nei] -= 1
                if ic[nei] == 0:
                    q.append(nei)
        return [i for i, n in enumerate(ic) if n == 0]