LeetCode-207. Course Schedule

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?

Example 1:

Input: 2, [[1,0]] Output: trueExplanation: 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: 2, [[1,0],[0,1]]Output: falseExplanation: 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.

题解：

使用拓扑排序。

先遍历所有路径，利用邻接表存储结点i的所有子节点。然后找出入度为0的结点，放入队列中，再把这个结点删除，删除它所有指向子节点的边，之后如果它的子节点入度为0，那同样放入队列中再次进行如上操作。最终判断路径长度是否等于课程数。

class Solution {public: bool canFinish(int numCourses, vector>& prerequisites) { int cnt = 0; vector> M(numCourses); vector inDegree(numCourses, 0); queue q; for (int i = 0; i < prerequisites.size(); i++) { M[prerequisites[i][1]].push_back(prerequisites[i][0]); inDegree[prerequisites[i][0]]++; } for (int i = 0; i < numCourses; i++) { if (inDegree[i] == 0) { q.push(i); } } while (q.empty() == false) { int tmp = q.front(); q.pop(); cnt++; for (int i = 0; i < M[tmp].size(); i++) { inDegree[M[tmp][i]]--; if (inDegree[M[tmp][i]] == 0) { q.push(M[tmp][i]); } } } return cnt == numCourses; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。