【C++解説】スワップ操作で seq[i] = i を最大化するプログラムの実装方法

問題概要

整数の順列 seq と、0 から n-1 までの整数を含むサイズ m の整数ペアの配列 pairs が与えられます。seq[i] = i（0 ≤ i < n） となる要素の数を最大化するため、次の操作を可能な限り何度でも実行できます。

• 整数 j（0 ≤ j < m）を 1 つ選び、seq[pairs[j] の最初の値] と seq[pairs[j] の 2 番目の値] を入れ替える。

操作を複数回行った後、seq[i] = i を満たす i の個数の最大値を求めてください。

入力例と出力例

たとえば、入力が n = 4、m = 2、seq = {0, 3, 2, 1}、pairs = {{0, 1}, {2, 3}} の場合、出力は 2 となります。このとき達成できる最大値は 2 です。

解法のアプローチ

この問題はグラフの連結成分として捉えることで解けます。スワップ可能な位置同士を辺で結んだ無向グラフを考えると、同じ連結成分内の要素は互いに自由に入れ替えられます。一方、異なる成分にまたがる移動は一切できないため、「値を行き先の位置へ届けられるか」は成分の所属だけで判定できます。

具体的な手順は以下の通りです。

1. 初期状態で既に seq[i] == i となっている要素の数を res としてカウントします。
2. pairs の各ペアを無向グラフの辺として隣接リスト vis に登録します。
3. DFS でグラフを連結成分ごとに分解し、各成分に一意の番号 idx を割り当てて tp 配列に記録します。
4. 各成分内の位置 j について、seq[j] の属する成分が j と同じで、かつ seq[j] != j ならば、スワップによって固定化できるため res を 1 増やします。
5. 最終的な res を出力します。

アルゴリズムの擬似コード

N := 100
サイズ N の配列 tp を定義
サイズ N の配列 vtmp, vis を定義

関数 dfs(j, k):
    tp[j] := k
    vtmp[k] の末尾に j を挿入
    vis[j] 内の各値 b について:
        tp[b] が 0 でない場合はスキップ
        dfs(b, k)

res := 0
i := 0 から n-1 まで:
    seq[i] == i ならば res を 1 増やす
i := 0 から m-1 まで:
    a := pairs[i] の最初の値
    b := pairs[i] の 2 番目の値
    vis[a] の末尾に b、vis[b] の末尾に a を挿入
idx := 1
i := 0 から n-1 まで:
    tp[i] == 0 ならば:
        dfs(i, idx)
        vtmp[idx] 内の各要素 j について:
            tp[seq[j]] == idx かつ seq[j] != j ならば res を 1 増やす
        idx を 1 増やす
res を出力

C++ での実装例

それでは、実際の実装を見ていきましょう。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
int tp[N];                     // 各頂点が属する連結成分の番号
vector<int> vtmp[N], vis[N];   // vtmp: 成分ごとのメンバー / vis: 隣接リスト

void dfs(int j, int k){
   tp[j] = k;
   vtmp[k].push_back(j);
   for(auto b : vis[j]) {
      if(tp[b] != 0)
         continue;
      dfs(b, k);
   }
}

void solve(int n, int m, int seq[], vector<pair<int, int>> pairs) {
   int res = 0;
   // 初期状態で seq[i] == i となる要素をカウント
   for(int i = 0; i < n; i++){
      if(seq[i] == i)
         res++;
   }
   // ペアを無向グラフの辺として登録
   for(int i = 0; i < m; i++){
      int a = pairs[i].first;
      int b = pairs[i].second;
      vis[a].push_back(b);
      vis[b].push_back(a);
   }
   int idx = 1;
   // 連結成分ごとに固定化できる要素を数える
   for(int i = 0; i < n; i++) {
      if(tp[i] == 0) {
         dfs(i, idx);
         for(auto j: vtmp[idx]){
            if(tp[seq[j]] == idx && seq[j] != j)
               res++;
         }
         idx++;
      }
   }
   cout << res;
}

int main() {
   int n = 4, m = 2, seq[] = {0, 3, 2, 1};
   vector<pair<int,int>> pairs = {{0, 1}, {2, 3}};
   solve(n, m, seq, pairs);
   return 0;
}

入力

4, 2, {0, 3, 2, 1}, {{0, 1}, {2, 3}}

出力

2

動作の確認（入力例）

入力例では、pairs = {{0, 1}, {2, 3}} より、連結成分は {0, 1} と {2, 3} の 2 つに分かれます。

• 初期状態で seq[0] = 0、seq[2] = 2 が成立しているため、まず res = 2。
• 成分 {0, 1} 内の位置 1 には値 3 がありますが、3 の本来の位置は別の成分に属するため移動できません。
• 成分 {2, 3} 内の位置 3 には値 1 がありますが、これも別の成分に属するため移動できません。

よって答えは 2 となります。

計算量

DFS による連結成分分解が O(n + m)、各要素の判定は合計で O(n) であるため、全体の計算量は O(n + m) となります。n と m が大きい場合でも高速に動作する効率的な解法です。