# 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