forked from shruti170901/Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Course Schedule II.cpp
38 lines (35 loc) · 941 Bytes
/
Course Schedule II.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
vector<int> findOrder(int n, vector<vector<int>>& pre) {
if(pre.size()==0){
vector<int> res(n);
for(int i=0; i<n; i++) res[i]=i;
return res;
}
vector<vector<int>> adj(n);
vector<int> indeg(n, 0);
for(int i=0; i<pre.size(); i++){
adj[pre[i][1]].push_back(pre[i][0]);
indeg[pre[i][0]]++;
}
queue<int> q;
for(int i=0; i<n; i++){
if(indeg[i]==0) q.push(i);
}
vector<int> ans;
while(!q.empty()){
int tp = q.front();
q.pop();
ans.push_back(tp);
for(auto c: adj[tp]){
indeg[c]--;
if(indeg[c]==0) q.push(c);
}
}
if (ans.size()==n){
return ans;
}else{
return vector<int>(0);
}
}
};