LeetCode课程表打卡（拓扑排序例题）

例题一：LeetCode ：207

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

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

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

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

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同

• const int N=2010;
  const int M=5010;
  class Solution {
  public:int h[N],e[M],ne[M],idx;int in[N];int cnt;void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}bool topsort(int n){queue<int>q;for(int i=0;i<n;i++){if(!in[i]){q.push(i);cnt++;}}while(q.size()){int t=q.front();q.pop();for(int i=h[t];~i;i=ne[i]){int j=e[i];in[j]--;if(!in[j]){q.push(j);cnt++;}}}if(cnt==n){return true;}else{return false;}}bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {memset(h,-1,sizeof(h));for(int i=0;i<prerequisites.size();i++){add(prerequisites[i][1],prerequisites[i][0]);in[prerequisites[i][0]]++;}if(topsort(numCourses)){return true;}else{return false;}}
  };

例题二：LeetCode：210

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

• 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：

输入：numCourses = 1, prerequisites = []
输出：[0]

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• 所有[ai, bi] 互不相同

• const int N=2010;
  const int M=N*(N-1);
  class Solution {
  public:int h[N],e[M],ne[M],idx;int cnt;int in[N];vector<int>ans;void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}bool topsort(int n){queue<int> q;for(int i=0;i<n;i++){if(!in[i]){q.push(i);}}while(q.size()){int t=q.front();q.pop();ans.push_back(t);cnt++;//cout<<cnt<<endl;for(int i=h[t];~i;i=ne[i]){int j=e[i];in[j]--;if(!in[j]){q.push(j);}}}if(cnt==n){return true;}else{return false;}}vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<int> res;memset(h,-1,sizeof(h));for(int i=0;i<prerequisites.size();i++){add(prerequisites[i][1],prerequisites[i][0]);in[prerequisites[i][0]]++;}if(topsort(numCourses)){return ans;}else{return res;}}
  };

 

 例题三：LeetCode：1462

你总共需要上 numCourses 门课，课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ，其中 prerequisites[i] = [ai, bi] 表示如果你想选 bi 课程，你 必须 先选 ai 课程。

• 有的课会有直接的先修课程，比如如果想上课程 1 ，你必须先上课程 0 ，那么会以 [0,1] 数对的形式给出先修课程数对。

先决条件也可以是 间接 的。如果课程 a 是课程 b 的先决条件，课程 b 是课程 c 的先决条件，那么课程 a 就是课程 c 的先决条件。

你也得到一个数组 queries ，其中 queries[j] = [uj, vj]。对于第 j 个查询，您应该回答课程 uj 是否是课程 vj 的先决条件。

返回一个布尔数组 answer ，其中 answer[j] 是第 j 个查询的答案。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
输出：[false,true]
解释：[1, 0] 数对表示在你上课程 0 之前必须先上课程 1。
课程 0 不是课程 1 的先修课程，但课程 1 是课程 0 的先修课程。

示例 2：

输入：numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
输出：[false,false]
解释：没有先修课程对，所以每门课程之间是独立的。

示例 3：

输入：numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
输出：[true,true]

提示：

• 2 <= numCourses <= 100
• 0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
• prerequisites[i].length == 2
• 0 <= ai, bi <= numCourses - 1
• ai != bi
• 每一对 [ai, bi] 都 不同
• 先修课程图中没有环。
• 1 <= queries.length <= 104
• 0 <= ui, vi <= numCourses - 1
• ui != vi

 这一题没用拓扑排序，用了Floyd，hh。

典型求闭包。

const int N=110;
class Solution {
public:int dis[N][N];vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {memset(dis,0x3f,sizeof(dis));vector<bool> ans;for(int i=0;i<numCourses;i++){dis[i][i]=0;}for(int i=0;i<prerequisites.size();i++){dis[prerequisites[i][0]][prerequisites[i][1]]=0;}for(int k=0;k<numCourses;k++){for(int i=0;i<numCourses;i++){for(int j=0;j<numCourses;j++){dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);}}}for(int i=0;i<queries.size();i++){if(!dis[queries[i][0]][queries[i][1]]){ans.push_back(true);}else{ans.push_back(false);}}return ans;}
};