-
Notifications
You must be signed in to change notification settings - Fork 0
/
210-course-schedule-ii.cpp
47 lines (47 loc) · 1.94 KB
/
210-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
39
40
41
42
43
44
45
46
47
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
// find courses without constraint requirements
int reqments[numCourses];
bool completed[numCourses];
vector<int> done;
for (int i = 0; i < numCourses; i++) {
reqments[i] = 0;
completed[i] = false;
}
for (int i = 0; i < prerequisites.size(); i++) {
reqments[prerequisites[i][0]]++;
}
for (int i = 0; i < numCourses; i++) {
if (reqments[i]==0){ // no requirements, get these courses done first
done.push_back(i);
completed[i] = true;
cout << i << " No reqs" << endl;
}
}
int prev = prerequisites.size();
// keep finishing courses as per `done` fulfilled
while (!(prerequisites.empty())){
for (int i = 0; i < prerequisites.size(); i++) {
if (reqments[prerequisites[i][0]]>0 && completed[prerequisites[i][1]]){
cout << prerequisites[i][0] << " Reqs left = " << reqments[prerequisites[i][0]] << endl;
if (reqments[prerequisites[i][0]]==1){
done.push_back(prerequisites[i][0]); // requirement fulfilled, so complete that course
completed[prerequisites[i][0]] = true; // completed
}
reqments[prerequisites[i][0]]--;
prerequisites.erase(prerequisites.begin()+i);
i--;
}
}
if(prev==prerequisites.size() && (!(prerequisites.empty()))){ // // not possible, ded end
cout << prerequisites.size() << " &" << endl;
done.clear();
break;
}
prev = prerequisites.size();
cout << prev << " &&" << endl;
}
return done;
}
};