leetcode_课程表（BFS、拓扑排序）

题目描述：

最近打华为软挑有用到拓扑剪枝，顺便刷了这题。
题目要求翻译过来就是要在一个有向图中找环：使用拓扑算法把入度为零的点去掉，再更新入度表，使用bfs循环往复，如果图中没有环，那最后不会有点留下来。
返回值很简洁，若去掉的点数量与总数不符，就是有漏网之鱼；

贴代码：

class Solution {

public:

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {

        vector<int> indegree(numCourses);//入度表

        vector<vector<int> > graph(numCourses);//邻接表

        vector<int> v;//用于初始化邻接表的各头节点

        for(int i=;i<numCourses;i++){//初始化入度表

            indegree[i]=;

            graph.push_back(v);

        }

        for(int i=;i<prerequisites.size();i++){

            indegree[prerequisites[i][]]++;

            graph[prerequisites[i][]].push_back(prerequisites[i][]);//将入点放入邻接表

        }

        queue<int> q;//入度为零的都放入队列

        for(int i=;i<numCourses;i++){

            if(indegree[i]==) q.push(i);

        }

        int cnt=;

        while(!q.empty()){//bfs消减入度

            int temp=q.front();

            q.pop();

            cnt++;

            for(int i=;i<graph[temp].size();i++){

                indegree[graph[temp][i]]--;

                if(indegree[graph[temp][i]]==){

                    q.push(graph[temp][i]);

                }

            }

        }

        return numCourses==cnt;

    }

};