Topological Sort - Find Eventual Safe States
The following code attempts to find eventual safe states using the reversed graph and Kahn's algorithm. Identify the line containing the subtle bug that causes incorrect results on some inputs.
from collections import deque
def eventualSafeNodes(graph):
n = len(graph)
reverse_graph = [[] for _ in range(n)]
in_degree = [0] * n
for u in range(n):
for v in graph[u]:
reverse_graph[v].append(u)
in_degree[u] = len(graph[u]) # Bug fixed here
queue = deque([i for i in range(n) if in_degree[i] == 0])
safe = []
while queue:
node = queue.popleft()
safe.append(node)
for prev in reverse_graph[node]:
in_degree[prev] -= 1
if in_degree[prev] == 0:
queue.append(prev)
return sorted(safe)
