Easy c++ solution 20ms beat 100% using dfs


  • 0
    W
    bool dfs(int start,vector<list<int>>&mat,vector<int>&color)
    {
        color[start] = 1;
        bool flag = true;
        
        for(std::list<int>::iterator it = mat[start].begin();it!=mat[start].end();++it)
        {
                if(color[*it] == 1)return false;
                if(color[*it] != 2)flag = dfs(*it,mat,color);
                if(!flag)return false;
        }
        color[start] = 2;
        
        return flag;
    }
    
    bool findcircle(vector<list<int>>& mat,vector<int>&color)
    {
        int siz = mat.size();
        bool flag=true;
        for(int i=0;i<siz;++i)
        {
            if(color[i]==0)flag = dfs(i,mat,color);
            if(!flag)return false;
        }
        
        return true;
    }
    
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        
        vector<int> color(numCourses,0);
        list<int> tmp;
        vector<list<int>> mat(numCourses,tmp);
        
        int len = prerequisites.size();
        
        for(int i=0;i<len;++i)
        {
            mat[prerequisites[i].first].push_front(prerequisites[i].second);
        }
        
        return findcircle(mat,color);
    }

Log in to reply
 

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