23.07.12 Today’s Leetcode

802. Find Eventual Safe States (medium)

Non-DFS Solution, Slow..

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:

        graph = [set(x) for x in graph]
        terminal = set()


        for index, edge in enumerate(graph):
            if not edge:
                terminal.add(index)
            
        n = len(graph)
        check = [False] * n
        for node in terminal:
            check[node] = True

        def help():
            nonlocal check
            for i in range(n):
                if not graph[i] - terminal:
                    terminal.add(i)

        prev = set()
        # it is similar to BFS, but this part is so weird..
        while terminal != prev:
            prev |= terminal
            help()

        return sorted(list(terminal))

DFS Solution

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        visited = [0] * n
        ans = set()

        def dfs(graph, x, visited, ans):
            visited[x] = 1
            if not graph[x]:
                ans.add(x)
                return True

            for i in graph[x]:
                if not visited[i]:
                    if not dfs(graph, i, visited, ans):
                        return False
                elif i not in ans:
                    return False

            ans.add(x)
            return True

        for i in range(n):
            if not visited[i]:
                dfs(graph, i, visited, ans)

        return sorted(list(ans))