topological sort c++: 9ms beat 97%


  • 0
    S
    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<int> indegree(numCourses,0);//kahn alg
            vector<vector<int>> adj(numCourses,vector<int>());
            for(auto dir:prerequisites) //initial indegree and adjacency list
            {
                indegree[dir.first]++;
                adj[dir.second].push_back(dir.first);
            }
            queue<int> que;//initialize queue with 0 indegree
            for(int i=0;i<indegree.size();i++)
            {
                if(0==indegree[i])
                    que.push(i);
            }
            int num_zero_deg = 0;
            while(!que.empty())
            {
                int u = que.front();
                que.pop();
                num_zero_deg++;
                for(auto v:adj[u])
                {
                    indegree[v]--;
                    if(indegree[v]==0)
                        que.push(v);
                }
                
            }
            
            if(num_zero_deg == numCourses)
                return true;
            else
                return false;
        }
    };

  • 0
    S

    dfs

    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            //depth first search
            //initialize visit and create adjacency list
            vector<int> visit(numCourses,0);//0->no visit  1->start visit  2->finish visit
            vector<vector<int>> graph(numCourses,vector<int>());
            for(auto pre:prerequisites)
                graph[pre.second].push_back(pre.first);
            
            bool cycle = false;
            for(int i=0;i<numCourses && visit[i]==0;i++)
            {
                dfs(graph,visit,i,cycle);
                if(cycle == true)
                    return false;
            }
            return true;
        }
    private:
        void dfs(vector<vector<int>>& graph,vector<int>& visit,int i,bool& cycle)
        {
            if(visit[i]==1) {cycle = true;return;}  //start visit but not finish
            if(visit[i]==0) 
            {
                visit[i]=1;
                for(auto adj:graph[i])
                {
                    dfs(graph,visit,adj,cycle);
                }
                visit[i] = 2;  //finish
            }
          
        }
    };

Log in to reply
 

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