C ++中的序列重建
假设我们必须检查是否可以从seqs中的序列唯一地重建原始序列org。原始序列是从1到n的整数的排列，并且n在1≤n≤10^4的范围内。在此，重建意味着使序列中的序列具有最短的公共超序列。我们必须检查是否只有一个序列可以从序列中重建出来，并且它是原始序列。
因此，如果输入类似于org=[1,2,3]，seqs=[[1,2,,[1,3]]，则输出将为false，因为[1,2,3]不是唯一可重构的序列，因为[1,3,2]也是可重构的有效序列。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数ok()，将采用v1，v2，
如果v1的大小不等于v2的大小，则-
返回假
对于初始化i：=0，当i<v1的大小时，更新（将i增加1），执行-
返回假
如果v1[i]不等于v2[i]，则-
返回真
从主要方法执行以下操作
n：=原始序列的大小
定义大小为（n+1）的数组图
定义一张映射度数
idx：=0
对于初始化i：=0，当i<seqs的大小时，更新（将i增加1），执行-
u：=seqs[i，j-1]
v：=seqs[i，j]
在图形的末尾插入v[u]
（将度数[v]增加1）
如果u>n或v>n或u<1或v<1，则-
返回假
indegree[seqs[i，0]]：=0
返回假
如果seqs[i]的大小>=1并且（seqs[i，0]>n或seqs[i，0]<1），则-
如果seqs[i]的大小>=1并且不调用indegree的count（seqs[i，0]），则-
对于初始化j：=1，当j<seqs[i]的大小时，更新（将j增加1），执行-
定义一个队列
对于初始化i：=1，当i<=n时，更新（将i增加1），-
将我插入q
如果我的度数是indegree并且indegree[i]等于0，则-
当（不是q为空）时，执行-
v：=graph[node，i]
（将度数[v]降低1）
如果indegree[v]等于0，则-
将v插入q
返回假
返回假
返回假
如果q>1的大小，则-
如果idx与org的大小相同，则-
节点：=q的第一个元素
从q删除元素
如果org[idx]不等于node，则-
（将idx增加1）
对于初始化i：=0，当i<graph[node]的大小时，更新（将i增加1），执行-
当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