- 找到最终的安全状态
在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。 如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。
现在, 如果我们最后能走到终点,那么我们的起始节点是最终安全的。 更具体地说, 存在一个自然数 K, 无论选择从哪里开始行走, 我们走了不到 K 步后必能停止在一个终点。
哪些节点最终是安全的? 结果返回一个有序的数组。
该有向图有 N 个节点,标签为 0, 1, …, N-1, 其中 N 是 graph 的节点数. 图以以下的形式给出: graph[i] 是节点 j 的一个列表,满足 (i, j) 是图的一条有向边。
示例:
输入:graph = [[1,2],[2,3],[5],[0],[5],[],[]]
输出:[2,4,5,6]
由于题目翻译原因 题目意思可能不太准确
**题目意思是 从一个节点的任何一个邻接的出发 不可能再次回到之前已经走过的节点 也就是不存在环 **
用DFS 递归每个节点的时候 应该检查每个节点的状态以便返回是否有环
用拓扑排序的话 因为题意指出了不存在环 也就是 最后会走到一个出度为0的节点才行 这里我们用出度作为标准 构建反向图即可 为什么要构建反向图 因为我们在传统的拓扑排序 是从入度为0的一个节点进入 在访问它邻接的节点 但是现在我们是从出度为0的节点倒着访问 所以说应该构建反向图来记录下是哪一个节点邻接于当前出度为0的节点
class Solution:
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
# 1 有环 2 无环 -1 当次搜索
# not graph[i]代表i没有邻接于任何一个节点 即为终点 是安全的
# def dfs(graph, i, visit):
# if visit[i] == 1: return False
# if visit[i] == 2 or not graph[i]: return True
# visit[i] = -1
# for child in graph[i]:
# if visit[child] == -1 or not dfs(graph, child, visit):
# visit[i] = 1
# return False
# visit[i] = 2
# return True
# n = len(graph)
# ans = []
# visit = [0]*n
# for i in range(n):
# if dfs(graph, i, visit):
# ans.append(i)
# return ans
# 题目意思为 从当前节点任何一个邻接的节点出发 不可能存在环
# 也就意味着 到最后出度必然为0 才能称之为安全
# 采用拓扑排序 以出度为标准 构建反向图
n = len(graph)
reGraph = defaultdict(list)
degree = [0]*n
for u, v in enumerate(graph): # 邻接表 表示u邻接于v 也就是u -> v
degree[u] += len(v) # 记录的是出度
for child in v:
reGraph[child].append(u)
queue = deque([i for i in range(n) if degree[i] == 0]) # 用的是双端队列
ans = []
while queue:
nowNode = queue.popleft()
ans.append(nowNode)
for child in reGraph[nowNode]:
degree[child] -= 1
if degree[child] == 0:
queue.append(child)
return sorted(ans) # 题目要求返回的列表有序
因为leetcode python3环境已经导入了collections 所以说对于defaultdict于deque是可以直接引用的