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

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

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