-
Notifications
You must be signed in to change notification settings - Fork 0
/
0207-course-schedule.cpp
44 lines (40 loc) · 1.1 KB
/
0207-course-schedule.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
#include<vector>
using namespace std;
class Solution {
private:
void dfs(int i, vector<vector<int>> &adj, vector<int> &indegrees) {
indegrees[i] = -1;
for (auto j: adj[i]) {
if (indegrees[j]>0&&(--indegrees[j] == 0)) {
dfs(j, adj, indegrees);
}
}
}
public:
bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
vector<vector<int>> adj(numCourses, vector<int>{});
vector<int> indegrees(numCourses, 0);
for (auto it: prerequisites) {
adj[it[1]].push_back(it[0]);
indegrees[it[0]]++;
}
for (int i = 0; i < numCourses; i++) {
if (indegrees[i] == 0) {
dfs(i, adj, indegrees);
}
}
for (auto i: indegrees) {
if (i > 0)return false;
}
return true;
}
};
int main() {
// vector<vector<int>> q {{1,0},{2,1}};
vector<vector<int>> q{{1, 4},
{2, 4},
{3, 1},
{3, 2}};
Solution s;
s.canFinish(5, q);
}