সি++ এ সিকোয়েন্স পুনর্গঠন

ধরুন আমাদের চেক করতে হবে মূল সিকোয়েন্স org কে seqs-এর ক্রম থেকে অনন্যভাবে পুনর্গঠন করা যায় কিনা। মূল ক্রম হল 1 থেকে n পর্যন্ত পূর্ণসংখ্যাগুলির একটি স্থানান্তর এবং 1 ≤ n ≤ 10^4 পরিসরে n। এখানে পুনর্গঠনের অর্থ হল সিক্যুয়েন্সগুলির একটি সংক্ষিপ্ততম সাধারণ সুপারসিক্যুয়েন্স তৈরি করা। আমাদের পরীক্ষা করতে হবে যে শুধুমাত্র একটি সিকোয়েন্স আছে যা 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)

• একটি মানচিত্র অসম্পূর্ণ সংজ্ঞায়িত করুন

• idx :=0

• আরম্ভ করার জন্য i :=0, যখন i

  • যদি seqs[i]>=1 এবং (seqs[i, 0]> n বা seqs[i, 0] <1) এর আকার হয়, তাহলে −

    • ফেরত মিথ্যা

  • যদি seqs[i]>=1 এর সাইজ হয় এবং কল কাউন্ট(seqs[i, 0]) না হয়, তাহলে -

    • indegree[seqs[i, 0]] :=0

  • j শুরু করার জন্য :=1, যখন j

    • u :=seqs[i, j - 1]

    • v :=seqs[i, j]

    • গ্রাফ[u]

      -এর শেষে v সন্নিবেশ করান

    • (1 দ্বারা indegree[v] বাড়ান)

    • যদি u> n বা v> n বা u <1 বা v <1, তাহলে −

      • মিথ্যা ফেরত দিন

• একটি সারি সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=1, যখন i <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

  • যদি i indegree এবং indegree[i] 0 এর সমান হয়, তাহলে −

    • q

      -এ ঢোকান

• যখন (q খালি নয়), −

  করুন

  • যদি q> 1 এর আকার হয়, তাহলে −

    • মিথ্যা ফেরত দিন

  • যদি idx org এর আকারের সমান হয়, তাহলে −

    • মিথ্যা ফেরত দিন

  • নোড :=q এর প্রথম উপাদান

  • q

    থেকে উপাদান মুছুন

  • যদি org[idx] নোডের সমান না হয়, তাহলে -

    • ফেরত মিথ্যা

  • (আইডিএক্স 1 দ্বারা বাড়ান)

  • আরম্ভ করার জন্য i :=0, যখন i <গ্রাফের আকার [নোড], আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), করুন −

    • v :=গ্রাফ[নোড, i]

    • (1 দ্বারা indegree[v] কমান)

    • যদি indegree[v] 0 এর সমান হয়, তাহলে −

      • q

        -এ v সন্নিবেশ করান

• 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