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

• ``````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;
}
};``````

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