| 4 | class Solution { |
| 5 | public: |
| 6 | vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { |
| 7 | int n=numCourses; |
| 8 | int m=prerequisites.size(); |
| 9 | vector<int>ans; |
| 10 | vector<int>v(n,0); |
| 11 | vector<vector<int>>g(n); |
| 12 | |
| 13 | |
| 14 | for(int i=0;i<m;i++){ |
| 15 | g[prerequisites[i][1]].push_back(prerequisites[i][0]); |
| 16 | v[prerequisites[i][0]]++; |
| 17 | } |
| 18 | queue<int>q; |
| 19 | for(int i=0;i<n;i++){ |
| 20 | if(v[i]==0){ |
| 21 | q.push(i); |
| 22 | } |
| 23 | } |
| 24 | int c=0; |
| 25 | while(!q.empty()){ |
| 26 | int j=q.front(); |
| 27 | q.pop(); |
| 28 | ans.push_back(j); |
| 29 | cout<<j<<" "; |
| 30 | c++; |
| 31 | for(int i=0;i<g[j].size();i++){ |
| 32 | v[g[j][i]]--; |
| 33 | //cout<<v[g[j][i]]<<" "; |
| 34 | if(v[g[j][i]]==0){ |
| 35 | |
| 36 | q.push(g[j][i]); |
| 37 | } |
| 38 | } |
| 39 | } |
| 40 | if(ans.size()!=n){ |
| 41 | return {}; |
| 42 | } |
| 43 | else{ |
| 44 | return ans; |
| 45 | } |
| 46 | } |
| 47 | }; |