2050. Parallel Courses III

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCoursej, nextCoursej] denotes that course prevCoursej has to be completed before course nextCoursej (prerequisite relationship). Furthermore, you are given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i+1)th course.

You must find the minimum number of months needed to complete all the courses following these rules:

• You may start taking a course at any time if the prerequisites are met.
• Any number of courses can be taken at the same time.

Return the minimum number of months needed to complete all the courses.

Note: The test cases are generated such that it is possible to complete every course (i.e., the graph is a directed acyclic graph).

class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        vector<int> req(time.begin(), time.end());
        vector<unordered_set<int>> topology(n);
        vector<int> rel(n);
        for(auto& vec: relations) {
            int from = vec[0] - 1, to = vec[1] - 1;
            topology[from].insert(to);
            rel[to]++;
        }
        queue<int> q;
        for(int i = 0; i < n; i++) {
            if(!rel[i]) {
                q.push(i);
            }
        }

        while(!q.empty()) {
            auto course = q.front(); q.pop();
            for(auto& nxt : topology[course]) {
                if(--rel[nxt] == 0) {
                    q.push(nxt);
                }
                req[nxt] = max(req[nxt], req[course] + time[nxt]);
            }
        }

        return *max_element(req.begin(), req.end());
    }
};