1136. Parallel Courses

基本上跟210. Course Schedule II 一模一樣, 就不多說明了

class Solution {
public:
  int minimumSemesters(int n, vector<vector<int>> &relations) {
    vector<int> indegree(n + 1, 0);
    vector<vector<int>> n_course(n + 1);
    for(int i = 0; i < relations.size();i++){
      indegree[relations[i][1]]++;
      n_course[relations[i][0]].push_back(relations[i][1]);
    }
    queue<int> q;
    int res = 0;
    for(int i = 0; i < indegree.size();i++){
      if(indegree[i] == 0){
        q.push(i);
      }
    }
    if(q.empty()) return -1;
    while(!q.empty()){
      int len = q.size();
      res++;
      for(int i = 0 ; i < len;i++){
        int cur = q.front();
        q.pop();
        for(auto next: n_course[cur]){
          indegree[next]--;
          if(indegree[next] == 0){
            q.push(next);
          }
        }
      }
    }
    for(int i = 0; i < indegree.size();i++){
      if(indegree[i] != 0) return -1;
    }
    return res;
  }
};