easy solution to judge whether there is a cycle


  • 0
    Z

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

Log in to reply
 

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