算法——图论：拓扑排序

. - 力扣（LeetCode）

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

即图中不能有环。

注意邻接表和邻接矩阵的转换。

自己的解法：拓扑排序，找出每个节点前面节点的个数，不断遍历将值为零的访问。

类似广度优先搜索，不过不完全一样，未使用队列，时间复杂度较高。

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {if(prerequisites.size()==0)return true;vector<long long> pre(numCourses,0);vector<int> visited(numCourses,0);for(int i=0;i<prerequisites.size();i++){int  a=prerequisites[i][0],b=prerequisites[i][1];pre[a]++;}int maxcou=numCourses;while(maxcou--){for(int i=0;i<numCourses;i++){if(visited[i]==0&&pre[i]==0){visited[i]=1;for(int j=0;j<prerequisites.size();j++){if(prerequisites[j][1]==i)pre[prerequisites[j][0]]--;}}}}for(int i=0;i<numCourses;i++){if(visited[i]==0)return false;}        return true;}
};

注意：在while循环中判断条件为课程数量，即最多可能循环这么多次。考虑极端情况:

5->4->3->2->1，第一次到最后才找到5，第二次到最后才找到4，这样每次循环只能访问一个节点。需n次。若为1->2->3->4->5，则仅需一次即可访问全部节点。

题目中使用的是邻接矩阵，或者转换一下使用邻接表，会更方便。

官方题解：

1.深搜

class Solution {
private:vector<vector<int>> edges;vector<int> visited;bool valid = true;public:void dfs(int u) {visited[u] = 1;for (int v: edges[u]) {if (visited[v] == 0) {dfs(v);if (!valid) {return;}}else if (visited[v] == 1) {valid = false;return;}}visited[u] = 2;}bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {edges.resize(numCourses);visited.resize(numCourses);for (const auto& info: prerequisites) {edges[info[1]].push_back(info[0]);}for (int i = 0; i < numCourses && valid; ++i) {if (!visited[i]) {dfs(i);}}return valid;}
};

2.广搜

使用一个队列；将邻接矩阵转化为邻接表。

class Solution {
private:vector<vector<int>> edges;vector<int> indeg;public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {edges.resize(numCourses);indeg.resize(numCourses);for (const auto& info: prerequisites) {edges[info[1]].push_back(info[0]);++indeg[info[0]];}queue<int> q;for (int i = 0; i < numCourses; ++i) {if (indeg[i] == 0) {q.push(i);}}int visited = 0;while (!q.empty()) {++visited;int u = q.front();q.pop();for (int v: edges[u]) {--indeg[v];if (indeg[v] == 0) {q.push(v);}}}return visited == numCourses;}
};