文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

總共有n個課程，從0到n-1。
有些課程可能有先決條件，例如，你想修課程0，你必須先修一門課程1，這兩門課之間的關系表示為:[0,1]

給定課程的總數(shù)和先決條件對的列表，返回你可以得到所有課程的不同方法的數(shù)量。

n <= 10樣例1 輸入: n = 2 prerequisites = [[1,0]] 輸出: 1 說明: 你必須按照0->1的順序上課。樣例2 輸入: n = 2 prerequisites = [] Output: 2 輸出: 你可以按0->1或1->0的順序上課。

https://tianchi.aliyun.com/oj/286601234951741590/302577566233072416

2. 解題

• 建圖，記錄出入度
• n 比較小，dfs 搜索

class Solution { public:/*** @param n: an integer, denote the number of courses* @param p: a list of prerequisite pairs* @return: return an integer,denote the number of topologicalsort*/int ans = 0;int topologicalSortNumber(int n, vector<vector<int>> &p) {// Write your code herevector<int> indegree(n, 0);vector<bool> vis(n, false);vector<vector<int>> g(n);for(auto& pi : p){indegree[pi[0]]++;g[pi[1]].push_back(pi[0]);}dfs(g, vis, indegree, 0);return ans;}void dfs(vector<vector<int>> &g, vector<bool>& vis, vector<int> &indegree, int count){if(count == g.size()){ans++;return;}for(int i = 0; i < g.size(); i++){if(vis[i]) continue;if(indegree[i]==0){vis[i] = true;for(auto nt : g[i])indegree[nt]--;dfs(g, vis, indegree, count+1);for(auto nt : g[i])indegree[nt]++;vis[i] = false;}}} };

2490ms C++

---

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

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的天池 在线编程 课程表（拓扑排序 + 回溯）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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