802.Find Eventual Safe States

In [1]:

import sys, random
sys.path.append("/home/swyoo/algorithm/")
from utils.verbose import logging_time
from typing import List
import numpy as np
sys.setrecursionlimit(100000)

Find Eventual Safe States

Which nodes are eventually safe? Return them as an array in sorted order. detail

Naive DFS

\(O((V + E)^2)\)

In [2]:

class Solution1:
    def __init__(self):
        self.isCycle = False
    @logging_time
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        def dfs(i):
            """ detect cycle. """
            seen[i] = True
            for j in graph[i]:
                if j not in seen:
                    dfs(j)
                elif j not in finish:
                    # print("detect cycle")
                    self.isCycle = True
                    return
            finish[i] = True

        ans = []
        for x in range(len(graph)):
            seen, finish = {}, {}
            self.isCycle = False
            dfs(x)
            if not self.isCycle:
                ans.append(x)
        return ans

sol1 = Solution1()

In [3]:

# graph = [[1,2],[2,3],[5],[0],[5],[],[]]
graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
print(sol1.eventualSafeNodes(graph, verbose=True))

WorkingTime[eventualSafeNodes]: 0.00978 ms
[4]

Improved DFS

I was inspired by a Youtube video.
The time complexity will be as follows. \(O((V + E))\)

In [4]:

class Solution2:
    @logging_time
    def eventualSafeNodes(self, graph):
        seen, finish, ans = set(), set(), set()
        def dfs(i):
            seen.add(i)
            for j in graph[i]:
                if j not in seen:
                    if dfs(j):
                        return True
                elif j not in finish:
                    # print("({} -> {}) edge makes cycle".format(i, j))
                    return True
            finish.add(i)
            ans.add(i)
            return False
        for x in range(len(graph)):
            if x not in seen:
                dfs(x)
        return sorted(list(ans))
sol2 = Solution2()

In [5]:

# graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
sol2.eventualSafeNodes(graph, verbose=True)

WorkingTime[eventualSafeNodes]: 0.00763 ms

[4]

Note:

• graph will have length at most 10000.
• The number of edges in the graph will not exceed 32000.
• Each graph[i] will be a sorted list of different integers, chosen within the range [0, graph.length - 1].

In [7]:

size, rate = 5000, 0.1
graph = []
for x in range(size):
    graph.append(list(np.random.choice(size, int(random.randint(0, size - 1) * rate), replace=False)))
    
print(sol1.eventualSafeNodes(graph, verbose=True))
print(sol2.eventualSafeNodes(graph, verbose=True))

WorkingTime[eventualSafeNodes]: 15085.39867 ms
[109, 377, 775, 1174, 1943, 2577, 3140, 3748, 4251]
WorkingTime[eventualSafeNodes]: 2.45190 ms
[109, 377, 775, 1174, 1943, 2577, 3140, 3748, 4251]

Summary

This problem is a similar problem with detect cycle in a directed graph.
I refered some pages.
If you want to know about more, please visit this documents as follows.

Reference

[1] Detect Cycle using topolgoical sort python implementation

In [None]: