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: 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.
判断有向图是否有环问题，第一个数字是顶点个数，数组表示两个端点的前后关系，后面顶点是前面顶点的前置条件。用拓扑排序解决这道题，如果拓扑排序之后，还剩下点，则表示有环。 拓扑排序过程：用邻接表来表示度，degree表示顶点的度数，找到图中入度为0的点，进行标记，删除以这些点为出度的边，及与这些点相连的顶点度数降低一，再次寻找入度为0的点，进行以上操作，循环n次（n为图中顶点个数）。
class Solution { public: bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { map<int, vector<int>> graph; vector<int> degree(numCourses, 0); for (int i = 0; i < prerequisites.size(); i++) { graph[prerequisites[i].second].push_back(prerequisites[i].first); degree[prerequisites[i].first]++; } for(int i = 0; i < numCourses; i++) { int j = 0; while(j < numCourses && degree[j] != 0) j++; if(j == numCourses) return false; degree[j] = -1; for(int k = 0; k < graph[j].size(); k++) degree[graph[j][k]]--; } return true; } };