C++-এ Sequence Reconstruction: অনুক্রম ইউনিকভাবে পুনর্নির্মাণযোগ্য কিনা যাচাই করা

আমাদের একটি মূল অনুক্রম (original sequence) org এবং কিছু সাব-সিকোয়েন্সের সমষ্টি seqs দেওয়া আছে। org হলো ১ থেকে n পর্যন্ত পূর্ণসংখ্যাগুলোর একটি পারমুটেশন। আমাদের যাচাই করতে হবে seqs গুলোর থেকে শুধুমাত্র org টিই ইউনিকভাবে রিকন্সট্রাক্ট (পুনর্নির্মাণ) করা সম্ভব কিনা। রিকন্সট্রাকশন মানে seqs গুলোর শর্টেস্ট কমন সুপারসিকোয়েন্স তৈরি করা।

উদাহরণ

ইনপুট: org = [1,2,3], seqs = [[1,2],[1,3]]

আউটপুট: false

কারণ: [1,2,3] একমাত্র সম্ভাব্য সিকোয়েন্স নয়, [1,3,2] ও একটি বৈধ সিকোয়েন্স যা seqs থেকে তৈরি করা যায়।

সমাধানের পদ্ধতি (Topological Sort / Kahn's Algorithm)

একটি গ্রাফ এবং ইনডিগ্রি (indegree) ম্যাপ তৈরি করুন।
seqs থেকে সব এজ (edge) বের করে গ্রাফ এবং ইনডিগ্রি আপডেট করুন। ইনভ্যালিড ভ্যালু (1 থেকে n বাইরে) থাকলে false রিটার্ন করুন।
ইনডিগ্রি ০ নোডগুলো একটি কিউতে রাখুন।
কিউ প্রসেস করুন:
- যদি কিউতে একাধিক নোড থাকে, তবে ইউনিক টপোলজিক্যাল অর্ডার সম্ভব নয় → false রিটার্ন করুন।
- নোড বের করে org এর সাথে মিলিয়ে নিন। মিল না হলে false।
- নোডের প্রতিটি নেইবারের ইনডিগ্রি কমিয়ে ০ হলে কিউতে পুশ করুন।
শেষে সব নোড প্রসেস হয়েছে কিনা (idx == org.size()) চেক করে true/false রিটার্ন করুন।

C++ কোড উদাহরণ

#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();
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3};
    vector<vector<int>> v1 = {{1,2},{1,3}};
    cout << (ob.sequenceReconstruction(v, v1));
    return 0;
}

ইনপুট

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