nikunjsoni

1136

Jul 10th, 2021
92
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int minimumSemesters(int n, vector<vector<int>>& relations) {
  4.         vector<int> indegree(n+1);
  5.         vector<vector<int>> graph(n+1);
  6.         for(auto edge: relations){
  7.             graph[edge[0]].push_back(edge[1]);
  8.             indegree[edge[1]]++;
  9.         }
  10.        
  11.         int level = 0, count=0;
  12.         queue<int> q;
  13.         for(int i=1; i<=n; i++){
  14.             if(!indegree[i])
  15.                 q.push(i);
  16.         }
  17.        
  18.         while(!q.empty()){
  19.             int sz = q.size();
  20.             count += sz;
  21.             for(int i=0; i<sz; i++){
  22.                 int curr = q.front(); q.pop();
  23.                 for(int next: graph[curr]){
  24.                     if(--indegree[next] == 0)
  25.                         q.push(next);
  26.                 }
  27.             }
  28.             level++;
  29.         }
  30.         return (count == n) ? level:-1;
  31.     }
  32. };
RAW Paste Data