[C++] Using 3 colored approach


  • 11
    A

    Here, i have used 3 colored approach. Here w -> represent white means vertex yet not visited.
    g -> gray , it means it is under DFS recursion and we again found the same node. This means cycle exists and return false.
    b -> black node when DFS is done visiting the node.
    This method checks cycle as well as keeps storing answer in stack in case cycle doesn't exists.

    class Graph {
        public:
        int v;
        list <int> *adj;
        Graph(int v)
        {
            this->v=v;
            adj = new list<int> [v];
        }
        void addedges(int src , int dest)
           {
    	     adj[dest].push_back(src);
           }	
    };
    class Solution {
    public:
        stack <int> st;
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            Graph g(numCourses);
            for (int i=0 ; i < prerequisites.size() ; i++)
                    g.addedges(prerequisites[i].first , prerequisites[i].second);        
            vector <int> ans;
            if(!courseScheduleCheck(g))
                    return ans;              
            while(!st.empty())
                {
                    ans.push_back(st.top());
                    st.pop();
                }
            return ans;       
        }
       bool courseScheduleCheck(Graph g)
        {
            int v = g.v;    
            vector <char> visit(v,'w');
            for(int i=0 ; i<v;i++)
            {        
               if(visit[i]== 'w')
                    if(iscycle(g,i,visit))
                        return false;
            }
            return true;
        }  
        bool iscycle(Graph g , int i, vector <char> & visit)
        {
            list <int> ::iterator it;
            for(it = g.adj[i].begin() ; it!=g.adj[i].end() ; it++)
            {
                if(visit[*it]== 'g')
                    return true;
                else
                {
                    if(visit[*it] != 'b')
                     {
                         visit[*it] = 'g';
                         if(iscycle(g,*it,visit))
                            return true;
                     }        
                }     
            }
             visit[i]='b';
             st.push(i);           
            return false;
        }            
    };

  • 0
    N

    Awesome solution! Innovative use of topological sort for detecting deadlock.


Log in to reply
 

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