2050. 並行課程 III

推薦事前閱讀：拓樸排序介紹

思路

課程有先後順序的完成要求，而完成課程需要花費的時間紀錄在times[i]當中。
舉個例子：課程有三堂：$[1,2,3]$，並且想要完成課程三，要先完成課程一與二。
完成三堂課程所需要的時間分別是 $[10,20,100]$。
因為可以同時修習課程的關係，最後完成全部課程需要的時間，是 $\max(10,20)+100$
能很容易的看出，「解鎖」某項課程所需的最少時間，是前置課程中花最多時間的那堂課。
因此，利用拓樸排序找到修習課程的順序，前置課程在「解鎖」後續課程時，更新後續課程需要花的最少時間。

程式碼

1. 鄰接表

class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        vector<int> indegree(n + 1); // 課程編號從 1 ~ n
        vector<vector<int>> graph(n + 1); // 鄰接表
        for(auto& v : relations) {
            graph[v[0]].push_back(v[1]);
            indegree[v[1]]++;
        }
        queue<int> q;
        vector<int> res(n + 1, 0);
        for(int i = 1; i <= n; i++) {
            if(indegree[i] == 0) {
                q.push(i);
                res[i] = time[i - 1]; // time[0] 對應課程 1 的時間
            }
        }
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(int v : graph[u]) {
                // u -> v, 更新 v 所需要花的時間
                res[v] = max(res[v], res[u] + time[v - 1]);
                if(--indegree[v] == 0) {
                    q.push(v);
                }
            }
        }
        return ranges::max(res);
    }
};

2. 鏈式前向星

推薦事前閱讀：鏈式前向星

class Solution {
private:
    static const int MAXN = 5e4+2; // MAXM = MAXN
    // 鏈式前向星
    int head[MAXN];
    int next[MAXN];
    int to[MAXN];
    int cnt;
    // 隊列
    int q[MAXN];
    // 入度表
    int indegree[MAXN];
    // 參考答案
    int res[MAXN];
    void build(int n) {
        cnt = 1;
        fill(head, head + n + 1, 0);
        fill(indegree, indegree + n + 1, 0);
        fill(res, res + n + 1, 0);
    }
    void addEdge(int u, int v) {
        to[cnt] = v;
        next[cnt] = head[u];
        head[u] = cnt++;
    }
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        build(n);
        for(auto& v : relations) {
            addEdge(v[0], v[1]);
            indegree[v[1]]++;
        }
        int l = 0, r = 0;
        for(int i = 1; i <= n; i++) {
            if(indegree[i] == 0) {
                res[i] = time[i - 1];
                q[r++] = i;
            }
        }
        while(l < r) {
            int u = q[l++];
            int v;
            for(int ei = head[u]; ei > 0; ei = next[ei]) {
                // u -> v, 更新 v 所需要花的時間
                v = to[ei];
                res[v] = max(res[v], res[u] + time[v - 1]);
                if(--indegree[v] == 0) {
                    q[r++] = v;
                }
            }
        }
        return ranges::max(res);
    }
};

複雜度分析

• 時間複雜度：$O(n+m)$
• 空間複雜度：$O(n+m)$