C++ solution, topilogical sort ,224ms


  • -1
    1
    struct Vert{
    int val;
    Vert* next;
    Vert(int v=0){val=v;next=NULL;};
    

    };

    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        const int num=numCourses;
        Vert course[num];
        int edges=prerequisites.size();
        pair<int,int> edge;
        for(int i=0;i<edges;++i){
            edge=prerequisites[i];
            ++course[edge.first].val;
            if(!course[edge.second].next){
                course[edge.second].next=new Vert;
                course[edge.second].next->val=edge.first;
            }
            else{
                auto ptr=course[edge.second].next;
                while(ptr->next)
                   ptr=ptr->next;
                ptr->next=new Vert;
                ptr->next->val=edge.first;
            }
        }
        stack<int> stk;
        for(int i=0;i<num;++i)
           if(course[i].val==0)
               stk.push(i);
        while(!stk.empty()){
            int tmp=stk.top();
            stk.pop();
            auto ptr=course[tmp].next;
            while(ptr){
                --course[ptr->val].val;
                if(course[ptr->val].val==0)
                    stk.push(ptr->val);
                ptr=ptr->next;
            }
        }
        for(int i=0;i<num;++i)
           if(course[i].val!=0)
              return false;
        return true;
    }

Log in to reply
 

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