Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.1 kB
1
Indexable
Never
class Solution {
public:
    int minNumberOfSemesters(int n, vector<vector<int>>& relations, int k) {
        vector<int> indegree(n+1,0);
        unordered_map<int,vector<int>> adjMap;
        for (auto r: relations) {
            indegree[r[1]]++;
            adjMap[r[0]].push_back(r[1]);
        }

        queue<int> q;
        int i=0; int j=1;
        while (i<k && j<=n) {
            if (indegree[j] == 0) {
                i++; q.push(j);  indegree[j] = -1;
            }
            j++;
        }

        int count = 0; int steps = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i=0; i<size; i++) {
                int u = q.front(); q.pop();
                count++;
                for (auto v: adjMap[u]) indegree[v]--;
            }
            steps++;

            int i = 0; int j = 1; 
            while (i<k && j<=n) {
                if (indegree[j] == 0) {
                    i++; q.push(j);  indegree[j] = -1;
                } 
                j++;
            }
        }
        return count == n ? steps : -1;
    }
};