802. Find Eventual Safe States

802. Find Eventual Safe States

 

Solution: DFS

concept:

যেই নোডগুলোতে সাইকেল নাই ওই গুলা প্রিন্ট করতে হবে।

Code:

class Solution {
public:
   
    unordered_set<int> cycle_nodes, safe_nodes;
   
    bool dfs(vector<vector<int>>& g, int i, unordered_set<int>visited_nodes)
    {
        if(safe_nodes.find(i) != safe_nodes.end())return true;
        if(cycle_nodes.find(i) != cycle_nodes.end())return false;
       
        if(visited_nodes.find(i) != visited_nodes.end()){
            cycle_nodes.insert(i);
            return false;
        }
       
        visited_nodes.insert(i);
        for(int node : g[i]){
            if(!dfs(g, node, visited_nodes)){
                cycle_nodes.insert(i);
                return false;
            }
        }
        safe_nodes.insert(i);
        return true;
    }
   
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        unordered_set<int>visited_nodes;
        vector<int>ans;
       
        for(int i = 0; i < graph.size(); i++){
            if(dfs(graph, i,visited_nodes))ans.push_back(i);
        }
        return ans;
    }
};

Share: