Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.3 kB
1
Indexable
Never
class Solution {

    bool bfs(int source , map<int,bool> &visited ,map<int, list<int>> &courses   ){
        map <int, int> parent;
        parent[source] =-1;
        visited[source] = 1;
        queue<int> q;
        q.push(source);
       
        while(!q.empty()){
            int node = q.front();
             for(auto neb: courses[node]){
                 if(visited[neb] == true && parent[node]!=neb){
                     return true;
                 }
                 else if(!visited[neb]){
                     visited[neb] = true;
                     q.push(neb);
                     parent[neb]= node;

                 }
             }
        }
        return false;
    }

public:

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        map<int, list<int>> courses;
        
        for(int i =0;i<prerequisites.size();i++){
            
                courses[prerequisites[i][0]].push_back(prerequisites[i][1]);
                courses[prerequisites[i][1]].push_back(prerequisites[i][0]);
        }
        map<int,bool> visited;
 
            for(int i =0 ;i<prerequisites.size();i++){
                if(!visited[i]){
                    bool ans = bfs(i,visited,courses);
                    return ans;
                }
            }

        return false;
    }
};