Minimum Time required to process all modules with interdependencies | OA | MUST DO | TRICKY

https://practice.geeksforgeeks.org/contest/gfg-weekly-coding-contest-98/problems/#

An IT companies working on a large project the project is broken into n module and distributed to different teams amount of time required to complete each module is given in an array duration modules can be processed simultaneously only if there is no dependency between them and it is given that M modules have interdependencies.
The project manager compute the minimum time required to complete the project.

Example 1:
Input:
6 6
1 2 3 1 3 2
5 2
5 0
4 0
4 1
2 3
3 1

Output:
8
Explaination:
At time 0, modules 5 and 4 are processed as they have no dependencies.
Module 5 finishes processing at time 2, allowing module 2 to begin processing at the same time.
At time 3, module 4 finishes processing and module 0 begins processing.
Module 0 finishes processing at time 4, allowing module 2 to finish processing at time 5.
Module 3 begins processing at time 5 and finishes at time 6, freeing up the resources for module 1 to start processing.
Module 1 finishes processing at time 8.

Example 2:
Input:
3 3
5 5 5
0 1
1 2
2 0

Output:
-1

Explaination: There is a cycle in the dependency graph hence the project cannot be completed.


---------------------------------------------------------------------------------------------------------------------------------------

class Solution {
    public:
    vector<int> adj[100001];

    int minTime(int n, int m, int duration[], vector<vector<int>>& dependency){
        vector<int> inDegree(n,0);
        for(auto edge: dependency){
            adj[edge[0]].push_back(edge[1]);
            inDegree[edge[1]]++;
        }
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
        for(int i=0;i<n;i++){
            if(inDegree[i]==0){
                pq.push({duration[i],i});
            }
        }
        int t=0;
        while(!pq.empty()){
            auto curr=pq.top();
            pq.pop();
            t+=(curr.first-t);
            for(auto nei: adj[curr.second]){
                inDegree[nei]--;
                if(inDegree[nei]==0){
                    pq.push({duration[nei]+t,nei});
                }
            }
        }
        for(int i=0;i<n;i++){ // there is no cycle if every node is checked
            if(inDegree[i]!=0){
                return -1;
            }
        }
        return t==0 ? -1 : t;
    }
};

-------------------------------------------------------------------------------------------------------------------------------------

class Solution {
public:
    int minTime(int n, int m, int duration[], vector<vector<int>>& dependency) {
        vector<vector<int>> adj(n);
        vector<int> deg(n, 0);
        for (auto x : dependency) {
            adj[x[0]].push_back(x[1]);
            deg[x[1]]++;
        }

        queue<int> q;
        vector<int> dp(n, 0);

        int count = 0;
        for (int i = 0; i < n; i++) {
            if (deg[i] == 0) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int node = q.front();
            q.pop();
            count++;

            for (int ngr : adj[node]) {
                if (--deg[ngr] == 0) {
                    q.push(ngr);
                }
                dp[ngr] = max(dp[ngr], dp[node] + duration[node]);
            }
        }

        int maxVal = -1;
        if (count == n) {
            for (int i = 0; i < n; i++) {
                maxVal = max(maxVal, dp[i] + duration[i]);
            }
        }

        return maxVal;
    }
};