C++ implementation of Kahn's topological sorting algorithm from Wikipedia


  • 0
    T
    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            // Kahn's topological sorting algorithm from Wikipedia
            // https://en.wikipedia.org/wiki/Topological_sorting
            
            // Make the graph
            int n = prerequisites.size();
            vector< vector<int> > edges;
            vector<int> numInEdges(numCourses, 0);
            edges.resize(numCourses);
            int i;
            for(i=0; i<n; i++)
            {
                edges[prerequisites[i].second].push_back(prerequisites[i].first);
                numInEdges[prerequisites[i].first] += 1;
            }
            
            // get the vertices without incoming edges
            int count = 0;
            queue<int> verticesNoInEdges;
            for(i=0; i<numCourses; i++)
            {
                if(numInEdges[i] == 0)
                {
                    verticesNoInEdges.push(i);
                    numInEdges[i] = -1;
                    count += 1;
                }
            }
            
            // Do the updating
            int node;
            while(verticesNoInEdges.size() > 0)
            {
                node = verticesNoInEdges.front();
                verticesNoInEdges.pop();
                for(i=0; i<edges[node].size(); i++)
                {
                    numInEdges[edges[node][i]] -= 1;
                    if(numInEdges[edges[node][i]] == 0)
                    {
                        verticesNoInEdges.push(edges[node][i]);
                        numInEdges[edges[node][i]]= -1;
                        count++;
                    }
                }
            }
            
            if(count == numCourses)
                return true; // DAG
            else
                return false;
        }
    };

Log in to reply
 

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