# 258ms cpp solution by using vector to represent a graph, and bfs to solve the problem

• ``````class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
{
int n = prerequisites.size();
if(n * numCourses == 0)
return true;
stack<int> zero;
vector<int> inDegree(numCourses, 0);
vector<vector<int> > graph(numCourses, vector<int>(0, 0));
for(int i = 0; i < n; i++)
{
int pre = prerequisites[i][0];
int after = prerequisites[i][1];
graph[pre].push_back(after);
inDegree[after]++;
}
for(int i = 0; i < numCourses; i++)
if(inDegree[i] == 0)
zero.push(i);
while(!zero.empty())
{
int take = zero.top();
zero.pop();
for(int i = 0; i < graph[take].size(); i++)
{
int after = graph[take][i];
inDegree[after]--;
if(inDegree[after] == 0)
zero.push(after);
}
}
for(int i = 0; i < numCourses; i++)
if(inDegree[i] != 0)
return false;
return true;
}
};``````

• It's amazing we almost share the same code. While there is no need to check the vector `inDegree` to find whether there exists left edges. Here, we can use the var `n`.

In the while loop, when you do the operation `inDegree[after]--;`, we make `--n;`

After the while loop, we just check whether `n` is zero or not. It not, there must have a cycle.

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