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,deque
class 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]-=1
if 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]==2
colors[node]=1
for subNode in graph[node]:
if not dfs(subNode):
return False
colors[node]=2
return True
# 第三步，执行递归，将各个未访问的节点的颜色进行标记，并根据最终的标记颜色返回结果
for i in range(length):
if colors[i]==0:
dfs(i)
return [t for t in range(length) if colors[t]==2]
4.执行结果
