# easy solution to judge whether there is a cycle

• use degree to save in-degree of the vertex, and use a map called edge to save the edges, each time we find a vertex whose in-degree is 0 and we delete this vertex and all edges comes from this vertex, then we try to find another vertex whose in-degree is 0, if we can not find it, then there exists a cycle in the graph and we can not finish all the courses. If every vertex was deleted from the map then we can finish all the courses.

``````class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<int> degree(numCourses,0);
map<int,vector<int>> edge;
for(int i=0;i<prerequisites.size();i++){
int first = prerequisites[i].first;
int second = prerequisites[i].second;
degree[second]+=1;
if(edge.find(first)==edge.end()){
vector<int> tmp(1,second);
edge[first] = tmp;
}
else{
edge[first].push_back(second);
}
}
vector<int> zero;
int hash[numCourses];
memset(hash,0,numCourses*4);
for(int i=0;i<numCourses;i++){
if(degree[i] == 0){
zero.push_back(i);
}
}
for(int i=0;i<zero.size();i++){
for(int j=0;j<edge[zero[i]].size();j++){
degree[edge[zero[i]][j]]-=1;
if(degree[edge[zero[i]][j]] == 0){
zero.push_back(edge[zero[i]][j]);
}
}
hash[zero[i]] = 1;
}
for(int i=0;i<numCourses;i++){
if(hash[i] == 0){
return false;
}
}
return true;
}
};
``````

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