HjHimansh

Course Schedule [in O(V+E)]

Jul 6th, 2020
93
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.    
  4.     vector<unordered_set<int>> make_graph(int numCourses, vector<vector<int>> &prerequisites){
  5.         vector<unordered_set<int>> myGraph(numCourses);
  6.         for(auto &x: prerequisites){
  7.             myGraph[x[1]].insert(x[0]);
  8.         }
  9.         return myGraph;
  10.     }
  11.    
  12.     bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
  13.         vector<unordered_set<int>> myGraph = make_graph(numCourses, prerequisites);    
  14.         vector<int> inDegrees(numCourses);
  15.        
  16.         for(auto &x: myGraph){
  17.             for(auto &y: x){
  18.                 inDegrees[y]++;        
  19.             }
  20.         }
  21.        
  22.         queue<int> q;
  23.        
  24.         int c = 0;
  25.        
  26.         for(int i=0; i<inDegrees.size(); i++){
  27.             if(inDegrees[i]==0){
  28.                 c++;
  29.                 q.push(i);
  30.             }
  31.         }
  32.        
  33.         while(!q.empty()){
  34.             //currently queue contains all the nodes with indegree of zero
  35.             //we have to pop them and update the neighbors indegrees and push them accordingly
  36.             int qSize = q.size();
  37.             while(qSize--){
  38.                 int fr = q.front();
  39.                 q.pop();
  40.                 for(auto &x: myGraph[fr]){
  41.                     inDegrees[x]--;
  42.                     if(inDegrees[x]==0){
  43.                         c++;
  44.                         q.push(x);
  45.                     }
  46.                 }                
  47.             }    
  48.         }
  49.        
  50.         //c is the count of the nodes which have final Indegree as 0
  51.         return (c==numCourses);
  52.     }
  53. };
RAW Paste Data Copied