LC-0802 Medium LeetCode

802. Find Eventual Safe States

Depth-First Search Breadth-First Search Graph Topological Sort

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 68% Topics: Depth-First Search, Breadth-First Search, Graph, Topological Sort

Reading material

Reference solution (spoiler · python)

# Time:  O(|V| + |E|)
# Space: O(|V|)

class Solution(object):
    def eventualSafeNodes(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[int]
        """
        WHITE, GRAY, BLACK = range(3)

        def dfs(graph, node, lookup):
            if lookup[node] != WHITE:
                return lookup[node] == BLACK
            lookup[node] = GRAY
            if any(not dfs(graph, child, lookup) for child in graph[node]):
                return False
            lookup[node] = BLACK
            return True

        lookup = [WHITE]*len(graph)
        return filter(lambda node: dfs(graph, node, lookup), xrange(len(graph)))

Solution from kamyu104/LeetCode-Solutions · MIT