1.题目基本信息
1.1.题目描述
有一个有 n 个节点的有向图，节点按 0 到 n – 1 编号。图由一个 索引从 0 开始 的 2D 整数数组 graph表示， graph[i]是与节点 i 相邻的节点的整数数组，这意味着从节点 i 到 graph[i]中的每个节点都有一条边。
如果一个节点没有连出的有向边，则该节点是 终端节点 。如果从该节点开始的所有可能路径都通向 终端节点 ，则该节点为 安全节点 。
返回一个由图中所有 安全节点 组成的数组作为答案。答案数组中的元素应当按 升序 排列。
1.2.题目地址
https://leetcode.cn/problems/find-eventual-safe-states/description/
2.解题方法
2.1.解题思路
逆向拓扑排序法 / DFS+三色染色法
2.2.解题步骤
DFS+三色染色法
- 第一步，定义并初始化各个节点的颜色。colors[i]==0，表示白色，还没有访问过；等于1，表示灰色，在递归栈中待着；等于2，黑色，安全的
- 第二步，构建dfs递归函数。递归任务：返回节点node是否安全
- 第三步，执行递归，将各个未访问的节点的颜色进行标记，并根据最终的标记颜色返回结果
逆向拓扑排序法
- 第一步，构建逆向图
- 第二步，拓扑排序
- 第三步，将拓扑排序的节点升序排列
3.解题代码
Python代码（逆向拓扑排序法）
from collections import defaultdict,dequeclass Solution:# 逆向拓扑排序法def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:length=len(graph)# 第一步，构建逆向图reverseGraph={i:[] for i in range(length)}inDegrees=defaultdict(int)for i in range(length):for node in graph[i]:reverseGraph[node].append(i)inDegrees[i]+=1# 第二步，拓扑排序result=[]que=deque()for node in reverseGraph.keys():if inDegrees[node]==0:que.append(node)result.append(node)while que:node=que.popleft()for subNode in reverseGraph[node]:inDegrees[subNode]-=1if inDegrees[subNode]==0:que.append(subNode)result.append(subNode)# 第三步，将拓扑排序的节点升序排列result.sort()return result
Python代码（DFS+三色染色法）
class Solution:# DFS+三色染色法def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:length=len(graph)# 第一步，定义并初始化各个节点的颜色。colors[i]==0，表示白色，还没有访问过；等于1，表示灰色，在递归栈中待着；等于2，黑色，安全的colors=[0]*length# 第二步，构建dfs递归函数。递归任务：返回节点node是否安全def dfs(node):if colors[node]!=0:return colors[node]==2colors[node]=1for subNode in graph[node]:if not dfs(subNode):return Falsecolors[node]=2return True# 第三步，执行递归，将各个未访问的节点的颜色进行标记，并根据最终的标记颜色返回结果for i in range(length):if colors[i]==0:dfs(i)return [t for t in range(length) if colors[t]==2]
4.执行结果
