文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

已知有 N 門課程，它們以 1 到 N 進(jìn)行編號。

給你一份課程關(guān)系表 relations[i] = [X, Y]，用以表示課程 X 和課程 Y 之間的先修關(guān)系：課程 X 必須在課程 Y 之前修完。

假設(shè)在一個學(xué)期里，你可以學(xué)習(xí)任何數(shù)量的課程，但前提是你已經(jīng)學(xué)習(xí)了將要學(xué)習(xí)的這些課程的所有先修課程。

請你返回學(xué)完全部課程所需的最少學(xué)期數(shù)。

如果沒有辦法做到學(xué)完全部這些課程的話，就返回 -1。

示例 1：

輸入：N = 3, relations = [[1,3],[2,3]] 輸出：2 解釋： 在第一個學(xué)期學(xué)習(xí)課程 1 和 2，在第二個學(xué)期學(xué)習(xí)課程 3。

示例 2：

輸入：N = 3, relations = [[1,2],[2,3],[3,1]] 輸出：-1 解釋： 沒有課程可以學(xué)習(xí)，因為它們相互依賴。提示： 1 <= N <= 5000 1 <= relations.length <= 5000 relations[i][0] != relations[i][1] 輸入中沒有重復(fù)的關(guān)系

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/parallel-courses
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

拓?fù)渑判?#xff1a;圖Graph–拓?fù)渑判?#xff08;Topological Sorting）

• 拓?fù)渑判蚰０孱}，入度為0的入隊

class Solution { public:int minimumSemesters(int N, vector<vector<int>>& relations) {unordered_map<int,unordered_set<int>> m;vector<int> indegree(N+1, 0);for(auto& re:relations){indegree[re[1]]++;m[re[0]].insert(re[1]);}queue<int> 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 finish==N ? sum : -1;} };

148 ms 26.3 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1136. 平行课程（拓扑排序）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。