Every day a Leetcode

題目來源：210. 課程表 II

解法1：

什么是拓撲排序？

我們考慮拓撲排序中最前面的節點，該節點一定不會有任何入邊，也就是它沒有任何的先修課程要求。當我們將一個節點加入答案中后，我們就可以移除它的所有出邊，代表著它的相鄰節點少了一門先修課程的要求。如果某個相鄰節點變成了「沒有任何入邊的節點」，那么就代表著這門課可以開始學習了。按照這樣的流程，我們不斷地將沒有入邊的節點加入答案，直到答案中包含所有的節點（得到了一種拓撲排序）或者不存在沒有入邊的節點（圖中包含環）。

上面的想法類似于廣度優先搜索，因此我們可以將廣度優先搜索的流程與拓撲排序的求解聯系起來。

算法：

代碼：

/** @lc app=leetcode.cn id=210 lang=cpp** [210] 課程表 II*/// @lc code=start// 拓撲排序（廣度優先搜索）class Solution
{
public:vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites){// 鄰接矩陣vector<vector<int>> graph(numCourses, vector<int>());// 入度數組vector<int> inDegree(numCourses, 0);vector<int> ans;// 初始化鄰接矩陣和入度數組for (vector<int> &p : prerequisites){graph[p[1]].push_back(p[0]);inDegree[p[0]]++;}queue<int> q;// 把入度為 0 的節點（即沒有前置課程要求）放在隊列中for (int i = 0; i < inDegree.size(); i++)if (inDegree[i] == 0)q.push(i);while (!q.empty()){// 每次從隊列中獲得節點，我們將該節點放在排序的末尾，// 并且把它指向的課程的入度各減 1int u = q.front();q.pop();ans.push_back(u);for (auto &v : graph[u]){inDegree[v]--;// 有課程的所有前置必修課都已修完（即入度為 0），// 我們把這個節點加入隊列中if (inDegree[v] == 0)q.push(v);}}// 當隊列的節點都被處理完時，說明所有的節點都已排好序，// 或因圖中存在循環而無法上完所有課程for (int &in : inDegree){// 不可能完成所有課程if (in != 0)return {};}return ans;}
};
// @lc code=end

結果：

復雜度分析：

時間復雜度: O(n+m)，其中 n 為課程數，m 為先修課程的要求數。這其實就是對圖進行廣度優先搜索的時間復雜度。

空間復雜度: O(n+m)。題目中是以列表形式給出的先修課程關系，為了對圖進行廣度優先搜索，我們需要存儲成鄰接表的形式，空間復雜度為 O(n+m)。在廣度優先搜索的過程中，我們需要最多 O(n) 的隊列空間（迭代）進行廣度優先搜索，并且還需要若干個 O(n) 的空間存儲節點入度、最終答案等。