例题一：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 <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites[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 <= 20000 <= prerequisites.length <= numCourses * (numCourses - 1)prerequisites[i].length == 20 <= ai, bi < numCoursesai != 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 <= 1000 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)prerequisites[i].length == 20 <= ai, bi <= numCourses - 1ai != bi- 每一对
[ai, bi]都 不同- 先修课程图中没有环。
1 <= queries.length <= 1040 <= ui, vi <= numCourses - 1ui != 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; } };
