# topological sort c++: 9ms beat 97%

• ``````class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<int> indegree(numCourses,0);//kahn alg
for(auto dir:prerequisites) //initial indegree and adjacency list
{
indegree[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++;
{
indegree[v]--;
if(indegree[v]==0)
que.push(v);
}

}

if(num_zero_deg == numCourses)
return true;
else
return false;
}
};``````

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