15.md

Find Eventual Safe States

METHOD 1(USING DIRECTING CYCLE) TLE

Node which are the part of cycle or lead to cycle will not in safe node

bool dfs(int i,vector<vector<int>>adj,vector<int>&visited,vector<int>&path,vector<int>&count)
    {
        visited[i]=1;
        path[i]=1;
        count[i]=0;
        
        for(auto it: adj[i])
        {
            if(!visited[it])
            {
                if(dfs(it,adj,visited,path,count)==true)
                {
                    count[i]=0;
                    return true;
                }
                    
            }
            //if the node has been previously visited but it has to be visited on the same path
            else if(path[it]==1)
            {
                count[i]=0;
                return true;
            }
        }
        count[i]=1;
        path[i]=0;
        return false;
    }
    
    vector<int> eventualSafeNodes(vector<vector<int>>& adj) {
        
        int V=adj.size();
        
        vector<int>visited(V,0);
        vector<int>path(V,0);
        vector<int>safe;
        vector<int>count(V,0);
        
        for(int i=0;i<V;i++)
        {
            if(!visited[i])
                dfs(i,adj,visited,path,count);
        }
        
        for(int i=0;i<V;i++)
            if(count[i]==1)
                safe.push_back(i);
        
        return safe;
                
    }

METHOD 2 (TOPO SORT BFS)

 vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        
        int V=graph.size();
        vector<int> adj[V];
        vector<int>indegree(V,0);
        
        for(int i=0;i<V;i++)
            for(auto it:graph[i])
            {
                adj[it].push_back(i);
                indegree[i]++;
            }
        
        queue<int>q;
        
        for(int i=0;i<V;i++)
            if(indegree[i]==0)
                q.push(i);
        
        if(q.size()==0)
            return {};
        
        vector<int>safe;
        
        while(!q.empty())
        {
            int node=q.front();
            q.pop();
            
            safe.push_back(node);
            
            for(auto it:adj[node])
            {
                indegree[it]--;
                if(indegree[it]==0)
                    q.push(it);
            }
        }
        
        sort(safe.begin(),safe.end());
        return safe;
    }