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


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

Log in to reply
 

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