सी ++ में अनुक्रम पुनर्निर्माण

मान लीजिए कि हमें यह जांचना है कि मूल अनुक्रम संगठन को seqs में अनुक्रमों से विशिष्ट रूप से पुनर्निर्मित किया जा सकता है या नहीं। मूल अनुक्रम 1 से n तक पूर्णांकों का क्रमपरिवर्तन है, और n श्रेणी 1 ≤ n ≤ 10^4 में है। यहां पुनर्निर्माण का अर्थ है seqs में अनुक्रमों का सबसे छोटा सामान्य सुपरसीक्वेंस बनाना। हमें यह जांचना होगा कि क्या केवल एक अनुक्रम है जिसे seqs से पुनर्निर्मित किया जा सकता है और वह मूल अनुक्रम है।

इसलिए, यदि इनपुट org =[1,2,3], seqs =[[1,2], [1,3]] जैसा है, तो आउटपुट गलत होगा, क्योंकि [1,2,3] नहीं है एकमात्र अनुक्रम जिसे फिर से बनाया जा सकता है, क्योंकि [1,3,2] भी एक मान्य अनुक्रम है जिसे फिर से बनाया जा सकता है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन को परिभाषित करें ठीक (), इसमें v1, v2,

  लगेगा

• यदि v1 का आकार, v2 के आकार के बराबर नहीं है, तो -

  • झूठी वापसी

• इनिशियलाइज़ i :=0 के लिए, जब i

  • अगर v1[i], v2[i] के बराबर नहीं है, तो -

    • झूठी वापसी

• सही लौटें

• मुख्य विधि से निम्न कार्य करें

• n :=मूल अनुक्रम का आकार

• आकार का एक सरणी ग्राफ़ परिभाषित करें (n + 1)

• एक मानचित्र को डिग्री में परिभाषित करें

• आईडीएक्स:=0

• प्रारंभ करने के लिए i:=0, जब i

  • यदि seqs[i]>=1 और (seqs[i, 0]> n या seqs[i, 0] <1) का आकार है, तो -

    • झूठी वापसी

  • अगर seqs[i]>=1 का आकार और डिग्री का कॉल काउंट (seqs[i, 0]) नहीं है, तो -

    • डिग्री [seqs[i, 0]] :=0

  • इनिशियलाइज़ j :=1 के लिए, जब j

    • यू :=seqs[i, j-1]

    • वी :=seqs[i, j]

    • ग्राफ़ के अंत में v डालें[u]

    • (इनडिग्री [v] 1 से बढ़ाएं)

    • यदि u> n या v> n या u <1 या v <1, तो -

      • झूठी वापसी

• एक कतार परिभाषित करें

• इनिशियलाइज़ i :=1 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), करें -

  • अगर मैं डिग्री में हूं और डिग्री [i] 0 के समान है, तो -

    • q में i डालें

• जबकि (नहीं q खाली है), करें -

  • यदि q> 1 का आकार है, तो -

    • झूठी वापसी

  • यदि idx, org के आकार के समान है, तो -

    • झूठी वापसी

  • नोड:=q का पहला तत्व

  • q से तत्व हटाएं

  • अगर org[idx] नोड के बराबर नहीं है, तो -

    • झूठी वापसी

  • (आईडीएक्स को 1 से बढ़ाएं)

  • प्रारंभ करने के लिए i:=0, जब i <ग्राफ का आकार [नोड], अद्यतन (i से 1 तक बढ़ाएं), करते हैं −

    • v :=ग्राफ [नोड, i]

    • (डिग्री [v] 1 से घटाएं)

    • अगर डिग्री [v] 0 के समान है, तो -

      • q में v डालें

• जब idx, org के आकार के समान हो, तो सही लौटें

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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