C++의 시퀀스 재구성

<시간/>

원래 시퀀스 org가 seqs의 시퀀스에서 고유하게 재구성될 수 있는지 확인해야 한다고 가정합니다. 원래 시퀀스는 1에서 n까지의 정수와 1 ≤ n ≤ 10^4 범위에 있는 n의 순열입니다. 여기서 재구성은 seqs에서 시퀀스의 가장 짧은 공통 수퍼 시퀀스를 만드는 것을 의미합니다. seq에서 재구성할 수 있는 시퀀스가 하나만 있는지 확인해야 하며 원래 시퀀스인지 확인해야 합니다.

따라서 입력이 org =[1,2,3], seqs =[[1,2],[1,3]]과 같으면 출력은 거짓이 됩니다. [1,3,2]도 재구성할 수 있는 유효한 시퀀스이기 때문에 재구성할 수 있는 유일한 시퀀스입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ok() 함수를 정의하면 v1, v2,
가 필요합니다.
v1의 크기가 v2의 크기와 같지 않으면 -
- 거짓 반환
initialize i :=0의 경우, i 를 수행합니다.
- v1[i]가 v2[i]와 같지 않으면 -
  - 거짓 반환
true를 반환
기본 방법에서 다음을 수행하십시오.
n :=원본 시퀀스의 크기
(n + 1) 크기의 배열 그래프 정의
하나의 맵을 차수로 정의
아이디:=0
for initialize i :=0, i
- seqs[i]>=1의 크기 및 (seqs[i, 0]> n 또는 seqs[i, 0] <1)인 경우 -
  - 거짓 반환
- seqs[i]의 크기>=1이고 indegree의 count(seqs[i, 0])를 호출하지 않으면 -
  - 차수[seqs[i, 0]] :=0
- j 초기화의 경우:=1, j
  - 유 :=seqs[i, j - 1]
  - v :=seqs[i,j]
  - 그래프 끝에 v 삽입[u]
  - (indegree[v] 1씩 증가)
  - u> n 또는 v> n 또는 u <1 또는 v <1이면 -
    - 거짓 반환
하나의 대기열 정의
initialize i :=1의 경우, i <=n일 때 업데이트(i를 1만큼 증가), −
- i가 indegree이고 indegree[i]가 0과 같으면 -
  - i를 q에 삽입
동안(q가 비어 있지 않음) -
를 수행합니다.
- 크기가 q> 1이면 -
  - 거짓 반환
- idx가 조직의 크기와 같으면 -
  - 거짓 반환
- node :=q의 첫 번째 요소
- q에서 요소 삭제
- org[idx]가 노드와 같지 않으면 -
  - 거짓 반환
- (idx를 1씩 증가)
- 초기화 i :=0의 경우, i <그래프[노드]의 크기일 때 업데이트(i를 1만큼 증가), 수행 -
  - v :=그래프[노드, i]
  - (indegree[v] 1 감소)
  - indegree[v]가 0과 같으면 -
    - v를 q에 삽입
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}}