Problem statement

https://leetcode.com/problems/find-eventual-safe-states/

Solution 1

What we actually need to find in this problem is all nodes, from which loops can be reached and then return all the rest nodes. There is a way to do it, using classical 3-colors dfs, where 0 stands for white and means we see this node first time, 1 means gray and means that we partially visited node and 2 means black and that we fully visited node.

Now, our dfs will work like this:

  1. If node is already visited, we check its color, and black color means that node is safe.
  2. Color node in gray, visit all neighbors. If color of neighbor is black, we do nothing. If it is gray or if this neighbor is not safe not dfs(nei), then we return False: our node is not safe.
  3. Finally, color node to fully visit and return 2. Note, that we color to black only in the very end, so if we see black node, we can be sure, that everything we can reach from this node also will be painted black.

Complexity

Complexity is O(V + E) for time and O(V) for space.

Code

class Solution(object):
    def eventualSafeNodes(self, graph):
        def dfs(node):
            if color[node] != 0:
                return color[node] == 2

            color[node] = 1
            for nei in graph[node]:
                if color[nei] == 2:
                    continue
                if color[nei] == 1 or not dfs(nei):
                    return False
            color[node] = 2
            return True
        
        n = len(graph)
        color = [0]*n
        return [i for i in range(n) if dfs(i)]

Solution 2

There is solution, where we use outgoing degrees: first, we create list of nodes with outgoing degrees equal to 0: we can be sure, that they are OK. Node is good if all outgoing edges going only go good nodes. So, we remove edges we already visited if they lead to good nodes. If it also happen that we have new node with zero outgoing degree, we put it in our queue. We can look at this solution as bfs.

Complexity

Complexity is O(V + E), both time and space.

Code

class Solution:
    def eventualSafeNodes(self, graph):
        n = len(graph)
        safe = [False] * n
        lgraph, rgraph = defaultdict(set), defaultdict(set)
        queue = deque()

        for i, nodes in enumerate(graph):
            if not nodes:
                queue.append(i)
            for j in nodes:
                lgraph[i].add(j)
                rgraph[j].add(i)
                
        while queue:
            j = queue.popleft()
            safe[j] = True
            for i in rgraph[j]:
                lgraph[i].remove(j)
                if len(lgraph[i]) == 0:
                    queue.append(i)

        return [i for i, v in enumerate(safe) if v]