leetcode 207. Course Schedule 图，检查有无环，拓扑序列

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Input: 2, [[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.

Input: 2, [[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.

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        int nSize = prerequisites.size();
        if(nSize == 0){
            return true;
        }
        
        int nTotal = 0;
        
        vector<int> degree(numCourses, 0);
        vector<vector<int>> G(numCourses);
        queue<int> q;
        
        // init the Graph
        for(int i = 0; i < prerequisites.size(); i++){
            degree[prerequisites[i][0]]++;
            G[prerequisites[i][1]].push_back(prerequisites[i][0]);
        }
        
        for(int i = 0; i < numCourses; i++){
            if(degree[i] == 0){
                q.push(i);      // 将第i门编号放入队列中
            }
        }
        
        while(!q.empty()){
            int t = q.front();
            q.pop();
            int edgesize = G[t].size();
            for(int i = 0; i < edgesize; i++){
                degree[G[t][i]]--;
                if(degree[G[t][i]] == 0){
                    q.push(G[t][i]);
                }
            }
            nTotal++;
        }
        
        if(nTotal != numCourses){
            return false;
        }
        return true;
    }
};