C++의 코스 일정 IV

우리가 수강할 수 있는 총 n개의 코스가 있다고 가정하고 코스는 0에서 n-1까지 레이블이 지정됩니다.

일부 과정에는 직접적인 전제 조건이 있을 수 있습니다. 예를 들어 과정 0을 수강하려면 먼저 과정 1을 수강해야 하며, 이는 [1,0] 쌍으로 표시됩니다.

따라서 코스가 n개 있는 경우 직접 선행 조건 쌍 목록과 쿼리 쌍 목록이 있습니다.

코스 쿼리[i][0]가 코스 쿼리[i][1]의 전제 조건인지 여부에 관계없이 각 쿼리[i]에 대한 답을 찾아야 합니다. 마지막으로 주어진 쿼리에 대한 답변인 부울 목록을 반환해야 합니다.

과정이 과정 b의 전제 조건이고 과정 b가 과정 c의 전제 조건이라면 과정은 과정 c의 전제 조건이라는 점을 명심해야 합니다.

따라서 입력이 n =3, 전제 조건 =[[1,2],[1,0],[2,0]], 쿼리 =[[1,0],[1,2]]인 경우 출력은 [true,true]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• N :=110

• ret 배열 정의

• 하나의 지도 정의

• v의 각 요소에 대해 수행

  • 그래프 끝에[1] 삽입[it[0]]

  • ([it[1]] 1씩 증가)

• 하나의 대기열 정의 q

• initialize i :=0의 경우, i

  • in[i]가 0과 같으면 -

    • i를 q에 삽입

• 하나의 맵 idx 정의

• initialize lvl :=1의 경우 q가 비어 있지 않으면 업데이트(lvl을 1만큼 증가)하고 -

  를 수행합니다.

  • sz :=q의 크기

  • sz가 0이 아닌 동안 각 반복에서 sz를 감소시키고 -

    • node :=q의 첫 번째 요소

    • q에서 요소 삭제

    • 그래프[노드]

      의 각 요소에 대해

      • (1만큼[it] 감소)

      • c[노드]의 각 요소 x에 대해 수행

        • c[it]

          에 x 삽입

      • c[it]

        에 노드 삽입

      • in[it]이 0과 같으면 -

        • q에 삽입

• x의 각 요소에 대해 수행

  • ret

    끝에 (c[it[1]]의 it[0] 빈도) 삽입

• 리턴 렛

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<bool> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
const int N = 110;
class Solution {
public:
   vector <int> graph[N];
   map <int, set <int>> c;
   vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& v, vector<vector<int>>& x) {
      vector<bool> ret;
      map<int, int> in;
      for (auto& it : v) {
         graph[it[0]].push_back(it[1]);
         in[it[1]]++;
      }
      queue<int> q;
      for (int i = 0; i < n; i++) {
         if (in[i] == 0)
            q.push(i);
      }
      map<int, int> idx;
      for (int lvl = 1; !q.empty(); lvl++) {
         int sz = q.size();
         while (sz--) {
            int node = q.front();
            q.pop();
            for (auto& it : graph[node]) {
               in[it]--;
               for (auto& x : c[node])
                  c[it].insert(x);
               c[it].insert(node);
               if (in[it] == 0) {
                  q.push(it);
               }
            }
         }
      }
      for (auto& it : x) {
         ret.push_back(c[it[1]].count(it[0]));
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> prerequisites = {{1,2},{1,0},{2,0}}, queries = {{1,0},{1,2}};
   print_vector(ob.checkIfPrerequisite(3, prerequisites, queries));
}

입력

3, {{1,2},{1,0},{2,0}}, {{1,0},{1,2}}

출력

[1, 1, ]