Untitled
unknown
c_cpp
2 years ago
1.3 kB
5
Indexable
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; } };
Editor is loading...