题意： 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.
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented. You may assume that there are no duplicate edges in the input prerequisites.click to show more hints. Hints:
This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort. Topological sort could also be done via BFS.思路：这题的主要目的是判断有向图中是否存在环，可以使用拓扑排序 的方法解决这道题，拓扑排序是用BFS的方法解决的，当然也可以使用DFS来检查是否存在环，先放python的使用拓扑排序的代码：
class Solution(object): def canFinish(self, numCourses, prerequisites): """ :type numCourses: int :type prerequisites: List[List[int]] :rtype: bool """ edge = {i:[] for i in xrange(numCourses)} for i in xrange(len(prerequisites)): edge[prerequisites[i][0]].append(prerequisites[i][1]) indegree = [0] * numCourses for i in edge: for j in edge[i]: indegree[j] += 1 stack = [] for i in xrange(numCourses): if indegree[i] == 0: stack.append(i) count = 0 while stack: cur = stack.pop() count += 1 for i in edge[cur]: indegree[i] -= 1 if indegree[i] == 0: stack.append(i) return False if count < numCourses else True还有一段使用dfs的c++的代码：
class Solution { public: bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { vector<unordered_set<int>> edge(numCourses); vector<bool> visited(numCourses,false); for (auto pre:prerequisites) edge[pre.first].insert(pre.second); for (int i = 0;i<numCourses;i++){ if(!dfs(edge,visited,i)) return false; } return true; } private: bool dfs(vector<unordered_set<int>> &edge,vector<bool> &visited,int node){ if (visited[node]) return false; else visited[node] = true; for (auto it = edge[node].begin();it!=edge[node].end();it++){ if(!dfs(edge,visited,*it)) return false; } visited[node] = false; return true; } };这里有个很关键的是visited[node] = false，意思很明确，比如有两条分叉路的时候，一条已经判断无环了，则分叉点visited又要置为0，让另一条分叉路得以继续判断。
