例题一: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;} };