C++でのシーケンスの再構築

元のシーケンス組織がseqsのシーケンスから一意に再構築できるかどうかを確認する必要があるとします。元のシーケンスは、1からnまでの整数の順列であり、nは1≤n≤10^4の範囲にあります。ここで、再構成とは、シーケンス内のシーケンスの最短の共通スーパーシーケンスを作成することを意味します。 seqsから再構築できるシーケンスが1つだけで、それが元のシーケンスであるかどうかを確認する必要があります。

したがって、入力がorg =[1,2,3]、seqs =[[1,2]、[1,3]]のような場合、[1,2,3]はそうではないため、出力はfalseになります。 [1,3,2]は再構築可能な有効なシーケンスでもあるため、再構築できる唯一のシーケンスです。

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

• 関数ok（）を定義します。これには、v1、v2、

  が必要です。

• v1のサイズがv2のサイズと等しくない場合、-

  • falseを返す

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

  • v1[i]がv2[i]と等しくない場合、-

    • falseを返す

• trueを返す

• メインの方法から次のようにします

• n：=元のシーケンスのサイズ

• サイズ（n + 1）の配列グラフを定義する

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

• idx：=0

• 初期化i：=0の場合、i <シーケンスのサイズの場合、更新（iを1増やします）、実行-

  • seqs [i]> =1かつ（seqs [i、0]>nまたはseqs[i、0] <1）のサイズの場合、-

    • falseを返す

  • seqs [i]> =1のサイズで、indegreeのcount（seqs [i、0]）を呼び出さない場合、-

    • indegree [seqs [i、0]]：=0

  • 初期化j：=1の場合、j

    • u：=seqs [i、j-1]

    • v：=seqs [i、j]

    • グラフの最後にvを挿入します[u]

    • （indegree [v]を1増やします）

    • u>nまたはv>nまたはu<1またはv<1の場合、-

      • falseを返す

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

• 初期化i：=1の場合、i <=nの場合、更新（iを1増やします）、実行-

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

    • iをqに挿入

• （qが空ではない）間、-

  • q> 1のサイズの場合、-

    • falseを返す

  • idxがorgのサイズと同じである場合、-

    • falseを返す

  • node：=qの最初の要素

  • qから要素を削除

  • org [idx]がnodeと等しくない場合、-

    • falseを返す

  • （idxを1増やします）

  • 初期化i：=0の場合、i <グラフ[ノード]のサイズの場合、更新（iを1増やします）、実行-

    • v：=グラフ[ノード、i]

    • （indegree [v]を1減らします）

    • indegree [v]が0と同じ場合、-

      • vをqに挿入

• idxがorgのサイズと同じ場合はtrueを返します

例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool ok(vector <int<& v1, vector <int<& v2){
      if (v1.size() != v2.size())
         return false;
      for (int i = 0; i < v1.size(); i++) {
         if (v1[i] != v2[i])
            return false;
      }
      return true;
   }
   bool sequenceReconstruction(vector<int<& org, vector<vector<int<>& seqs){
      int n = org.size();
      vector<int< graph[n + 1];
      unordered_map<int, int> indegree;
      int idx = 0;
      for (int i = 0; i < seqs.size(); i++) {
         if (seqs[i].size() >= 1 && (seqs[i][0] > n || seqs[i][0] < 1))
            return false;
         if (seqs[i].size() >= 1 && !indegree.count(seqs[i][0])) {
            indegree[seqs[i][0]] = 0;
         }
         for (int j = 1; j < seqs[i].size(); j++) {
            int u = seqs[i][j - 1];
            int v = seqs[i][j];
            graph[u].push_back(v);
            indegree[v]++;
            if (u > n || v > n || u < 1 || v < 1)
               return false;
         }
      }
      queue<int< q;
      for (int i = 1; i <= n; i++) {
         if (indegree.count(i) && indegree[i] == 0) {
            q.push(i);
         }
      }
      while (!q.empty()) {
         if (q.size() > 1) {
            return false;
         }
         if (idx == org.size()) {
            return false;
         }
         int node = q.front();
         q.pop();
         if (org[idx] != node) {
            return false;
         }
         idx++;
         for (int i = 0; i < graph[node].size(); i++) {
            int v = graph[node][i];
            indegree[v]--;
            if (indegree[v] == 0) {
               q.push(v);
            }
         }
      }
      return idx == org.size();
   }
};
main(){
   Solution ob;
   vector<int< v = {1,2,3};
   vector<vector<int<> v1 = {{1,2},{1,3}};
   cout << (ob.sequenceReconstruction(v, v1));
}

入力

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

出力

0