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:
解题思路：拓扑排序模版题。
class Solution { public: bool topologicalSort(int& numCourses,vector<vector<int>>& G,vector<int>& degree){ int num=0; queue<int>q; for(int i=0;i<numCourses;i++){ if(!degree[i])q.push(i); } while(!q.empty()){ int u=q.front(); q.pop(); for(int i=0;i<G[u].size();i++){ if(--degree[G[u][i]]==0){ q.push(G[u][i]); } } num++; } return num==numCourses; } bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { vector<vector<int>>G(numCourses); vector<int>degree(numCourses,0); for(int i=0;i<prerequisites.size();i++){ G[prerequisites[i].second].push_back(prerequisites[i].first); degree[prerequisites[i].first]++; } return topologicalSort(numCourses,G,degree); } };
原文：http://www.cnblogs.com/tsunami-lj/p/7632566.html