Medium

Find Eventual Safe States

LAB

Given a directed graph adjacency list, return all nodes that cannot reach a cycle, sorted ascending.

EXAMPLES

Example 1

Input
{
  "graph": [
    [
      1,
      2
    ],
    [
      2,
      3
    ],
    [
      5
    ],
    [
      0
    ],
    [
      5
    ],
    [],
    []
  ]
}

Output
[
  2,
  4,
  5,
  6
]

FUNCTION SHAPE

graph: intMatrix→intArray

SOLUTION NOTE

To solve the problem, we must first consider when a node is safe or unsafe. If we begin at any node and proceed along any path from that node, we will eventually reach either a terminal node or enter a cycle and continue to loop in it without ever reaching a terminal node.

Basically there's cycles that will not lead to a terminal node. If this was a dag answer is every node. We basically just have every node, except the ones in the cycles.

Reverse edges. Then do top sort. Intuition: start from terminal nodes like 5,6. Visit the nodes that point to them (ex. 2,4). If removing that edge we travelled on makes 2,4 terminal nodes, 2,4 MUST be safe. Continue this.

Basically think of it recursively. Safe nodes are defined recursively. Base case are terminal nodes. Terminal nodes are trivially safe. Consider the nodes that point to terminal nodes. Ignoring those edges, if the node has no more outgoing edges (it is now terminal) it must be safe. Constructs the safe nodes level by level, starting from terminal nodes.

Interesting problem, showcasing how we sometimes need to think in reverse.

Reveal reference solution +

pythonREFERENCE

# 1. reverse edges + kahn's top sort
# O(n+m) time and space.
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
    rgraph = defaultdict(list)
    n = len(graph)

    indegree = defaultdict(int) # this is after reversal. ie. outdegree of original graph
    for i in range(n):
        for nbr in graph[i]:
            rgraph[nbr].append(i)
            indegree[i] += 1

    q = deque([i for i in range(n) if indegree[i] == 0])

    safe = set()
    while q:
        curr = q.popleft()

        # add to safe since it is terminal
        safe.add(curr)

        for nbr in rgraph[curr]:
            indegree[nbr] -= 1

            if indegree[nbr] == 0: q.append(nbr)

    return [i for i in range(n) if i in safe]

TimeO(V + E)

SpaceO(V + E)

Open on LeetCode ↗