C++でのコーススケジュールIV

受講できるコースが合計n個あるとすると、コースには0からn-1までのラベルが付けられます。

一部のコースには直接的な前提条件がある場合があります。たとえば、コース0を受講するには、最初にコース1を受講する必要があります。これは、ペアとして表されます：[1,0]。

したがって、コースの数がnの場合、直接の前提条件のペアのリストとクエリのペアのリストがあります。

コースクエリ[i][0]がコースクエリ[i][1]の前提条件であるかどうかにかかわらず、各クエリ[i]の答えを見つける必要があります。最後に、ブール値のリスト、指定されたクエリへの回答を返す必要があります。

コースaがコースbの前提条件であり、コースbがコースcの前提条件である場合、コースaはコースcの前提条件であることに注意する必要があります。

したがって、入力がn =3のようである場合、前提条件=[[1,2]、[1,0]、[2,0]]、クエリ=[[1,0]、[1,2]]、出力は[true、true]

これを解決するには、次の手順に従います-

• N：=110

• 配列retを定義する

• で1つのマップを定義する

• vの要素ごとに、実行します

  • グラフの最後にit[1]を挿入します[it[0]]

  • （in [it [1]]を1増やします）

• 1つのキューを定義するq

• 初期化i：=0の場合、i

  • in [i]が0と同じ場合、-

    • iをqに挿入

• 1つのマップIDXを定義する

• 初期化レベル：=1の場合、qが空でない場合は、更新（レベルを1増やします）、実行-

  • sz：=qのサイズ

  • szが0でない場合は、反復ごとにszを減らし、-

    を実行します。

    • node：=qの最初の要素

    • qから要素を削除

    • 各要素について、graph [node]

      にあります

      • （in [it]を1つ減らします）

      • c [node]の要素xごとに、実行

        • xをc[it]

          に挿入します

      • ノードをc[it]

        に挿入します

      • in [it]が0と同じ場合、-

        • qに挿入

• x内の要素ごとに、実行します

  • retの最後に（c [it [1]]のit[0]の頻度）を挿入します

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

#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, ]