207. Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.
Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
 

Constraints:

1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All the pairs prerequisites[i] are unique.

这题是一个有向图的题目，让我们求一个有向图是否有环。我这里采取了BFS的遍历方式。

首先我们构造一个表达图的数组，每个元素分别是当前元素指向的下一个元素。然后我们需要计算每个元素被指向的次数。

有了这些数据之后，我们根据课程数量进行循环，找出一个没有被任意节点指向的节点，在上述的数据结构中，我们就是需要找出被指向的个数为0的节点。找不出来的话，说明剩下的元素有环，相互指向，直接返回即可。

找出了没有被指向的节点之后，我们把此节点剔除，并且把其被指向的次数置为-1,下次不会再次取此节点。同时把它指向的节点的被指向数-1。这里我们也可以理解为从图中把一个起始节点给拿走了，那么剩下的数据，肯定是该起始节点被指向节点的被指向数应该减去一。

如此往复，直到遍历完成后都满足条件，则此图没有环。

class CourseSchedule : public Solution {
public:
    void Exec() {
        
    }

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> courses(numCourses, vector<int>());
        for (auto &vec : prerequisites) {
            courses[vec[0]].push_back(vec[1]);
        }
        vector<int> indegrees(numCourses, 0);
        for (auto &v : prerequisites) {
            indegrees[v[1]]++;
        }

        for (int i = 0; i < numCourses; i++) {
            int inCourse = -1;
            for (int j = 0; j < numCourses; j++) {
                if (indegrees[j] == 0) {
                    inCourse = j;
                    break;
                }
            }
            if (inCourse < 0) return false;
            indegrees[inCourse] = -1;
            for (auto neigh : courses[inCourse]) {
                indegrees[neigh]--;
            }
        }
        return true;
    }
};