C++ में अनुक्रम पुनर्निर्माण - अद्वितीय पुनर्निर्माण की जांच

समस्या विवरण

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

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

समाधान दृष्टिकोण

टोपोलॉजिकल सॉर्ट (कान का एल्गोरिदम) का उपयोग करके:

1. एक फ़ंक्शन ok() परिभाषित करें जो दो वैक्टर की तुलना करता है
2. ग्राफ और इनडिग्री मैप बनाएं
3. seqs से किनारे (edges) निकालकर ग्राफ बनाएं
4. कतार (queue) में उन नोड्स को डालें जिनकी इनडिग्री 0 है
5. यदि किसी भी बिंदु पर कतार में एक से अधिक नोड्स हैं, तो false लौटाएं (एकाधिक विकल्प)
6. क्रमिक रूप से नोड्स को प्रोसेस करें और org से तुलना करें
7. अंत में जांचें कि क्या सभी नोड्स प्रोसेस हो गए

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}}

आउटपुट

0