Sequence Reconstruction - Kiểm tra chuỗi gốc có được tái tạo duy nhất từ các chuỗi con

Cho chuỗi gốc org (hoán vị của 1..n) và tập các chuỗi seqs. Kiểm tra xem org có phải là chuỗi siêu chung ngắn nhất duy nhất có thể tái tạo từ seqs hay không.

Ví dụ: org = [1,2,3], seqs = [[1,2],[1,3]] → kết quả false vì cả [1,2,3] và [1,3,2] đều hợp lệ.

Giải thuật (Topological Sort - Kahn)

Xây dựng đồ thị có hướng từ seqs, tính bậc vào. Thực hiện topological sort: nếu tại bất kỳ bước nào hàng đợi có > 1 phần tử → không duy nhất. Kiểm tra thứ tự lấy ra có khớp org không.

Cài đặt 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 v : graph[node]) {
                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;
}

Đầu vào

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

Đầu ra

0