Leetcode Algorithm 207. Course Schedule

Course Schedule 给定n门课程，以及一系列的课程对[a,b]，表示修课程a之前必须修完课程b，判断n门课程能否满足此依赖关系

解题思路

这是一道经典的拓扑排序问题，解法有两种：一种是每次从图中取出入度为0的节点，直到无入度为0的节点为止，判断是否有剩余节点；另一种是采用深度优先遍历的方法，判断图中是否有环。下面介绍第一种解法。

但是输入的形式并不是传统的邻接矩阵和邻接表，而是边列表，所以第一步是从边列表上构建图，可以用

vector<vector<int> > graph;

的形式构建一个邻接表，构建表的同时可以统计入度表。

邻接表构建完成之后，扫描一遍入度表，把入度为0的节点放进队列中。

每次取出对头，把其相邻的节点的入度减1，一旦入度减少到0，则把其放入队列当中。

当队列为空时，检验弹出的节点数是否与课程总数一致，若一致，则返回true，否则返回false。

代码与测试样例

#include <iostream> #include <vector> #include <queue> using namespace std; class Solution { public: bool canFinish(int numCourses, vector<pair<int, int> >& prerequisites) { vector<int> indegree(numCourses); vector<vector<int> > graph(numCourses); for (int i = 0; i < prerequisites.size(); i++) { graph[prerequisites[i].second].push_back(prerequisites[i].first); indegree[prerequisites[i].first]++; } queue<int> q; for (int i = 0; i < numCourses; i++) { if (indegree[i] == 0) q.push(i); } int count = 0; while (!q.empty()) { count++; int front = q.front(); for (int i = 0; i < graph[front].size(); i++) { indegree[graph[front][i]]--; if (indegree[graph[front][i]] == 0) q.push(graph[front][i]); } q.pop(); } return count == numCourses; } }; int main() { vector<pair<int, int> > prerequisites; prerequisites.push_back(pair<int, int>(1, 0)); int n = 2; Solution s; string result; result = s.canFinish(n, prerequisites) ? "true" : "false"; cout << result << endl; prerequisites.push_back(pair<int, int>(0, 1)); result = s.canFinish(n, prerequisites) ? "true" : "false"; cout << result << endl; return 0; }

输出

true false