Link: https://leetcode.com/problems/find-eventual-safe-states/
Solution:
Topics: topological order
Intuition
Very nice topological order problem. This one took me a couple attempts before finding an efficient enough solution, although I had the right idea from the start.
The key idea is basically to do a cycle detection on each node. If there exists a cycle starting at that node, it is not a safe node. We can use a classic visiting/visited pattern here.
Implementation
def safe_states(graph):
def cycle(node, visiting, visited):
if node in visiting:
return True
if node in visited:
return False
visiting.add(node)
for child in graph[node]:
if cycle(child, visiting, visited):
return True
visiting.remove(node)
visited.add(node)
return False
res = []
visiting = set()
visited = set()
for node in range(len(graph)):
if not cycle(node, visiting, visited):
res.append(node)
return res
#time: o(nm)
#memory: o(nm)Review 1
Fun little problem. Solved this one fast on first try…no idea why it took me a couple tries last time I solved this. Can also be solved with kahn’s algorithm.