Untitled
unknown
plain_text
2 years ago
1.1 kB
3
Indexable
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; } };
Editor is loading...