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?
For example:
2, [[1,0]]There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]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.
思路：实际上这道题就是判断图中有没有环存在。若有环，则课程是互为条件的，所以不可能，否则就是可能的。 使用拓扑排序算法，每次找到一个入度为0的点，将这个点加入序列中，然后将这个点所指向的点的入度变为0。 如果存在环，则这个环最终不会被加入序列中，因为互为环的节点入度不可能在拓扑排序算法中变为0。 代码如下： class Solution { public: bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { int * in_deg; in_deg=new int[numCourses]; for(int i=0;i<numCourses;i++) in_deg[i]=0; for(int i=0;i<prerequisites.size();i++) in_deg[prerequisites[i].first]++; queue<int> q; for(int i=0;i<numCourses;i++) if(in_deg[i]==0) q.push(i); int count=q.size(); while(!q.empty()){ int temp=q.front(); q.pop(); for(int i=0;i<prerequisites.size();i++){ if(temp==prerequisites[i].second){ in_deg[prerequisites[i].first]--; if(in_deg[prerequisites[i].first]==0){ q.push(prerequisites[i].first); count++; } } } } return count == numCourses; } };