leetcode-training/cpp/course-schedule.cpp at master · ldcduc/leetcode-training · GitHub

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
/* Problem url: https://leetcode.com/problems/course-schedule
 * Code by: ldcduc
 * */
/* Begin of Solution */
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        queue<int> Q;
        vector<vector<int>> pre(numCourses);
        vector<int> deg(numCourses, 0);
        for (auto item : prerequisites) {
            ++ deg[item[0]];
            pre[item[1]].push_back(item[0]);
        }
        for (int i = 0; i < numCourses; ++ i) {
            if (deg[i] == 0) {
                Q.push(i);
            }
        }
        int learnedCourses = 0;
        if (Q.empty()) {
            return false;
        } else {
            int course;
            while (!Q.empty()) {
                course = Q.front();
                Q.pop();
                ++ learnedCourses;
                for (auto item : pre[course]) {
                    -- deg[item];
                    if (deg[item] <= 0) {
                        Q.push(item);
                    }
                }
            }
        }
        return learnedCourses == numCourses;
    }
};
/* End of Solution */
/*
 * Comment by ldcduc
 * Suggested tags: queue
 *
 * */