leetcode 210. Course Schedule II [Medium]

davidlei included in leetcode

2021-12-23 179 words One minute

Contents

題目敘述

給一個 prerequisites，每個元素 prerequisites[i] = [a, b]，都代表如果想選 a 課程，必須先修過 b 課程。題目要求回傳可能的修課順序，如果不可能修過全部的課程，回傳一個空的陣列。

思考

什麼情況下會導致無法修過全部的課程? 考慮以下組合為例

prerequisites[0] = (1, 0), 修課程 1 之前必須修過課程 0
prerequisites[1] = (2, 1), 修課程 2 之前必須修過課程 1
prerequisites[2] = (0, 2), 修課程 0 之前必須修過課程 2

如果轉成有向圖則會變成以下情況

所以說這題其實是一題圖論的題目，把修課的條件建立成一個 graph，然後用 dfs 去尋訪，如果偵測到 cycle 代表一定有課程沒辦法修到，回傳空陣列。

在 dfs 的過程中用 status 來紀錄每個節點的狀態，如果 status[cur] == 1，代表這個節點是目前尋訪的點，用 status 來判斷是否有 cycle 的存在。

解題紀錄

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        
        // 建立有向圖
        for (const auto &requisite: prerequisites) {
            graph[requisite[1]].push_back(requisite[0]);
        }
        
        vector<int> order;
		// 紀錄節點狀態
        vector<int> travel_status(numCourses, 0);
        
        for (int course = 0; course < numCourses; course++) {
            if (!dfs(course, graph, travel_status, order)) return {};
        }
        
        reverse(order.begin(), order.end());
        return order;
    }
    
    // If return ture, mean graph has cycle.
    bool dfs(int cur, vector<vector<int>> &graph, 
             vector<int> &status, vector<int> &order) {
        if (status[cur] == 1) return false;
        if (status[cur] == 2) return true;
        
        // 目前正在拜訪 cur 節點
        // 如果後續又再次 dfs 到 cur 節點，代表 cycle 存在 return false
        status[cur] = 1;
        
        for (const int target: graph[cur]) {
            if (!dfs(target, graph, status, order)) return false;
        }
        
        status[cur] = 2;
        order.push_back(cur);
        return true;
    }
};