dede网站模板 音响,网站支付端口,建设南大街小学网站,做去态网站要学什么语言文章目录1. 题目2. 解题1. 题目
已知有 N 门课程#xff0c;它们以 1 到 N 进行编号。
给你一份课程关系表 relations[i] [X, Y]#xff0c;用以表示课程 X 和课程 Y 之间的先修关系#xff1a;课程 X 必须在课程 Y 之前修完。
假设在一个学期里#xff0c;你可以学习任…
文章目录1. 题目2. 解题1. 题目
已知有 N 门课程它们以 1 到 N 进行编号。
给你一份课程关系表 relations[i] [X, Y]用以表示课程 X 和课程 Y 之间的先修关系课程 X 必须在课程 Y 之前修完。
假设在一个学期里你可以学习任何数量的课程但前提是你已经学习了将要学习的这些课程的所有先修课程。
请你返回学完全部课程所需的最少学期数。
如果没有办法做到学完全部这些课程的话就返回 -1。
示例 1
输入N 3, relations [[1,3],[2,3]]
输出2
解释
在第一个学期学习课程 1 和 2在第二个学期学习课程 3。示例 2
输入N 3, relations [[1,2],[2,3],[3,1]]
输出-1
解释
没有课程可以学习因为它们相互依赖。提示
1 N 5000
1 relations.length 5000
relations[i][0] ! relations[i][1]
输入中没有重复的关系来源力扣LeetCode 链接https://leetcode-cn.com/problems/parallel-courses 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
拓扑排序图Graph–拓扑排序Topological Sorting
拓扑排序模板题入度为0的入队
class Solution {
public:int minimumSemesters(int N, vectorvectorint relations) {unordered_mapint,unordered_setint m;vectorint indegree(N1, 0);for(auto re:relations){indegree[re[1]];m[re[0]].insert(re[1]);}queueint q;int cur, size, sum 0, finish 0;for(int i 1; i N; i)if(indegree[i] 0)q.push(i);while(!q.empty()){size q.size();while(size--){cur q.front();q.pop();finish;for(auto it m[cur].begin(); it ! m[cur].end(); it){if(--indegree[*it] 0)q.push(*it);}}sum;}return finishN ? sum : -1;}
};148 ms 26.3 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
