C++でシーケンスを一意に再構築できるか判定する方法

この記事では、与えられた部分シーケンスの集合 seqs から、元のシーケンス org を一意に再構築できるかどうかを判定する問題をC++で解く方法を解説します。

問題の概要

元のシーケンス org は、1からnまでの整数の順列です。ここで n の範囲は 1 ≤ n ≤ 10^4 とします。「再構築」とは、seqs 内のシーケンスすべての最短共通超列（shortest common supersequence）を作ることを意味します。つまり、seqs から再構築できるシーケンスがただ1つであり、それが元のシーケンス org と一致するかどうかを確認する必要があります。

入力例

例えば、入力が org = [1,2,3]、seqs = [[1,2],[1,3]] の場合を考えてみましょう。このとき出力は false になります。なぜなら、[1,2,3] は再構築できる唯一のシーケンスではないからです。[1,3,2] もまた有効な再構築結果となり得るためです。

解法のアプローチ：トポロジカルソート

この問題は、グラフ理論におけるトポロジカルソートの考え方を使うことで効率的に解けます。各シーケンス内の隣接する要素間に「u → v」という有向辺を張り、その上で一意なトポロジカル順序が存在するかを確認します。具体的には、以下の手順に従います。

1. まず、seqs 内の各シーケンスについて、隣接する2要素 u と v の間に有向辺 u → v を追加し、v の入次数（indegree）を1増やします。
2. このとき、要素が範囲 [1, n] 外であれば、直ちに false を返します。
3. 入次数が0のノードをキューに入れます。
4. キューを処理する際、常にキュー内の要素数が1以下である必要があります。2つ以上の候補があるということは、順序が一意に定まらないことを意味するため、false を返します。
5. 取り出したノードが org[idx] と一致しない場合も false を返します。
6. 最後に、処理したノード数 idx が org のサイズと一致していれば true を返します。

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

計算量について

このアルゴリズムの時間計算量は O(V + E)、空間計算量も O(V + E) となります。ここで V はノード数（最大 n）、E は seqs から構築される辺の総数です。n が最大10^4程度であれば十分高速に動作します。

まとめ

シーケンスの一意な再構築可能性の判定は、「隣接要素から有向グラフを構築し、トポロジカルソートの順序が常に一意であること」を確認することで実現できます。キュー内の候補が複数になった時点で順序が確定しないため false を返すのがポイントです。競技プログラミングや技術面接でも頻出のパターンなので、ぜひマスターしておきましょう。