802. Find Eventual Safe States

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/find-eventual-safe-states
• topics: Graph, Recursion, DFS

Description

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).

Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.

Idea

• Straightforward DFS with memoization

Code

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:        
        visited = set()
 
        @cache
        def is_safe(i):
            if not graph[i]:
                return True
            if i in visited:
                return False
 
            visited.add(i)
            for adj in graph[i]:
                if not is_safe(adj):
                    return False
            visited.remove(i)
            return True
 
        return [i for i in range(len(graph)) if is_safe(i)]