解题思路
广度优先搜索
建立依赖关系图：[a,b] 表示课程a依赖于课程b，此时图中由b节点指向a节点即： b->a；
首先为所有应节点建立邻接表adjacents，建立计数器count统计节点中不为入度不为0的个数；然后统计图中入度为0的节点，将所有入度为0的节点加入到队列queue中。
当队列queue不为空时：
首先获取队列中的首节点pre，并通过邻接表访问与pre相连的节点，并将相连节点的入度减1；如果入度减1后，该节点的入度为0，则将该节点加入到队列中。最后将pre从队列中弹出，同时count减1。
最后，当count不为0时，说明存在节点未加入队列，说明遍历所有pre节点，都无法将某个节点的入度减为0，即该节点处于环中，不符题目，返回false；当count为0时，说明所有节点都加入队列，并已从队列中弹出，返回true。
代码
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> inDegree(numCourses,0);//记录所有顶点的入度
vector<vector<int>> adjacents(numCourses); //邻接表
queue<int> nodeQ;
int counts = numCourses;
for(auto &&node:prerequisites){
inDegree[node[0]]++;//入顶点
adjacents[node[1]].push_back(node[0]);//出顶点
}
for(int i=0;i<numCourses;i++){
//入度为0的先入队列
if(inDegree[i] == 0) nodeQ.push(i),counts--;
}
while(!nodeQ.empty()){
int pre = nodeQ.front();
for(auto&& ajNode:adjacents[pre]){
inDegree[ajNode]--;
if(inDegree[ajNode] == 0)
nodeQ.push(ajNode),counts--;
}
nodeQ.pop();// pop out
}
if(counts != 0) return false;
return true;
}
};
结果
执行用时：8 ms, 在所有 C++ 提交中击败了99.80%的用户
内存消耗：12.9 MB, 在所有 C++ 提交中击败了85.46%的用户
