Find Eventual Safe States


  • 0

    Click here to see the full article post


  • 0
    V

    Why am I getting TLE on last few test cases. It uses DFS to find cycle.

    class Solution {
    public:
        vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
            unordered_set<int> cycleNodes;
            vector<int> safeNodes;
            for(int i=0; i < graph.size(); i++) {
                vector<bool> visited(graph.size(), false);
                findCycles(i, graph, cycleNodes, visited);
            }
            for(int i=0; i<graph.size(); i++) {
                if(cycleNodes.find(i) == cycleNodes.end()) {
                    safeNodes.push_back(i);
                }
            }
            return safeNodes;
        }
        
        bool findCycles(int node, vector<vector<int>>& graph, unordered_set<int> &cycleNodes, vector<bool> &visited) {
            if(cycleNodes.find(node) != cycleNodes.end()) {
                return true;
            }
            if(visited[node] == true) {
                cycleNodes.insert(node);
                return true;
            }
            visited[node] = true;
            for(int i=0; i<graph[node].size(); i++) {
                bool isCycle = findCycles(graph[node][i], graph, cycleNodes, visited);
                if(isCycle) {
                    cycleNodes.insert(node);
                    return true;
                }
            }
            visited[node] = false;
            return false;
        } 
    };
    

  • 0
    E

    @vigjadel It's probably due to below sloc. We should preserve the visited states to avoid doing redundant dfs. Try moving this line above for loop.

    vector<bool> visited(graph.size(), false);


  • 0
    V

    Had to do 2 optimizations

    1. visited array was getting created on every iteration
    2. When node is black I can stop further computation.
    class Solution {
    public:
        vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
            vector<int> color(graph.size(), 0);
            vector<int> safeNodes;
            for(int i=0; i < graph.size(); i++) {
                findCycles(i, graph, color);
            }
            for(int i=0; i<graph.size(); i++) {
                if(color[i] == 3) {
                    safeNodes.push_back(i);
                }
            }
            return safeNodes;
        }
        
        bool findCycles(int node, vector<vector<int>>& graph, vector<int> &color) {
            if(color[node] == 2) {
                return true;
            }
            if(color[node] == 3) {
                return false;
            }
            if(color[node] == 1) {
                color[node] = 2;
                return true;
            }
            color[node] = 1;
            for(int i=0; i<graph[node].size(); i++) {
                bool isCycle = findCycles(graph[node][i], graph, color);
                if(isCycle) {
                    color[node] = 2;
                    return true;
                }
            }
            color[node] = 3;
            return false;
        } 
    };
    

  • 0
    V

    We can further optimize it by removing a redundant color

    class Solution {
    public:
        vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
            vector<int> color(graph.size(), 0);
            vector<int> safeNodes;
            for(int i=0; i < graph.size(); i++) {
                findCycles(i, graph, color);
            }
            for(int i=0; i<graph.size(); i++) {
                if(color[i] == 2) {
                    safeNodes.push_back(i);
                }
            }
            return safeNodes;
        }
        
        bool findCycles(int node, vector<vector<int>>& graph, vector<int> &color) {
            if(color[node] == 2) {
                return false;
            }
            if(color[node] == 1) {
                return true;
            }
            color[node] = 1;
            for(int i=0; i<graph[node].size(); i++) {
                bool isCycle = findCycles(graph[node][i], graph, color);
                if(isCycle) {
                    return true;
                }
            }
            color[node] = 2;
            return false;
        } 
    };
    

  • 0
    K

    Thanks for your excellent solution and explanation!


  • 0
    K

    here are my modified solution based on your explanation.

    class Solution {
        public List<Integer> eventualSafeNodes(int[][] graph) {
            List<Integer> res = new ArrayList<>();
            if(graph == null || graph.length == 0)  return res;
            
            int nodeCount = graph.length;
            int[] color = new int[nodeCount];
            
            for(int i = 0;i < nodeCount;i++){
                if(dfs(graph, i, color))    res.add(i);
            }
            
            return res;
        }
        public boolean dfs(int[][] graph, int start, int[] color){
            if(color[start] != 0)   return color[start] == 1;
            
            color[start] = 2;
            for(int newNode : graph[start]){
                if(!dfs(graph, newNode, color))    return false;
            }
            color[start] = 1;
            
            return true;
        }
    }
    

  • 0

    In Approach #2, Why do we need to skip current iteration while traversing the neighbors ? I attempted the code without

    if (color[node] == 2)
        continue;
    

    and it got accepted


  • 0
    R

    @ATM-SALEH Because when the color of its neighbour is BLACK, we know it's been visited and it's safe(will lead to a terminal state). We don't have to do redundant dfs traversal.


  • 0
    S

    @awice, @raynow, @ATM-SALEH: so we should check the condition "color[nei] == 2" instead of the condition "color[node] == 2".


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.