Leetcode 207. Course Schedule

source url

题目描述

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?

输入：课程数量，以及各课程前序课程的pair 输出：是否能完成课程 如：

Input: 2, [[1,0]] 2, [[1,0],[0,1]] Output: true false Explain: 上述输入2中，两个课程互为前序课程，无法完成

思路

简单来说，这是判断有向图中是否产生环路。这里选择使用拓扑排序的方式来检查，如果无法完成拓扑排序，也就是该课程有向图中产生了环路，即无法完成。 选用Kahn算法。

L← Empty list that will contain the sorted elements S ← Set of all nodes with no incoming edges while S is non-empty do remove a node n from S insert n into L foreach node m with an edge e from nto m do remove edge e from thegraph ifm has no other incoming edges then insert m into S if graph has edges then return error (graph has at least onecycle) else return L (a topologically sortedorder)

代码

class Solution { public: set<int> s; bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { int comingEdge[numCourses] = {0}; list<int> graph[numCourses]; int n,m;//node: n-e->m //build the list and counting comingEdge for(int i=0;i<prerequisites.size();i++){ n = prerequisites[i].second; m = prerequisites[i].first; //cout<<"m=="<<m<<" n=="<<n<<endl; comingEdge[m]++; graph[n].push_back(m); } //init Set S for(int i =0;i<numCourses;i++){ if(comingEdge[i]==0) s.insert(i); } while(!s.empty()){ int nodeN = *s.begin(); s.erase(nodeN); maintainSet(nodeN,graph[nodeN],comingEdge); } return isNoComingEdge(comingEdge,numCourses); } void maintainSet(int n, list<int>& graph,int* comingEdge){ //cout<<n<<" pop:"; while(graph.size()!=0){ int m = graph.front(); //cout<<m; graph.pop_front(); comingEdge[m]--; if(comingEdge[m]==0){ s.insert(m); } } //cout<<endl; } bool isNoComingEdge(int* comingEdge, int numCourses){ for(int i =0;i<numCourses;i++){ if(comingEdge[i]!=0){ //cout<<"i:"<<" "<<comingEdge[i]<<endl; return false; } } return true; } };