C++で靴下のすべてのペアを一緒に配置するために必要なスワップの最小数を見つけるためのプログラム

行と呼ばれる番号のリストがあり、これが一列に並んでいる靴下を表しているとします。並べ替えはしていませんが、靴下の各ペアが（0、1）、（2、3）、（4、5）のように並んでいるように並べ替えます。それらを再配置するために必要なスワップの最小数を見つける必要があります。

したがって、入力がrow =[0、5、6、2、1、3、7、4]のような場合、行の順序は2であるため、出力は2になります

• [0、5、6、2、1、3、7、4]

• [0、1、6、2、5、3、7、4]

• [0、1、3、2、5、6、7、4]

• [0、1、3、2、5、4、7、6]

これを解決するには、次の手順に従います-

• 配列pと別の配列szを定義します

• 関数find（）を定義します。これにはuが必要です

• return（p [u]がuと同じ場合はu、それ以外の場合はfind（p [u]）およびp [u]：=find（p [u]））

• 関数join（）を定義します。これには、u、v、

  が必要です。

• pu：=find（（u）、pv：=find（v））

• puがpvと同じ場合、-

  • 戻る

• sz [pu]> =sz [pv]の場合、-

  • p [pv]：=pu

  • sz [pu]：=sz [pu] + sz [pv]

• それ以外の場合

  • p [pu]：=pv

  • sz [pv]：=sz [pv] + sz [pu]

• メインの方法から、次のようにします-

• n：=arrのサイズ

• p：=サイズnの配列

• 初期化i：=0の場合、i

  • p [i]：=i

• sz：=サイズnの配列で、1で埋める

• 初期化i：=0の場合、i

  • u：=arr [i / 2] / 2

  • v：=arr [（i / 2）OR 1] / 2

  • join（u、v）

• ans：=0

• 初期化i：=0の場合、i

  • find（i）がiと同じ場合、-

    • ans：=ans + sz [i] − 1

  • ansを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
vector<int> p, sz;
int find(int u) {
   return p[u] == u ? u : p[u] = find(p[u]);
}
void join(int u, int v) {
   int pu = find(u), pv = find(v);
   if (pu == pv)
   return;
   if (sz[pu] >= sz[pv]) {
      p[pv] = pu;
      sz[pu] += sz[pv];
   }else {
      p[pu] = pv;
      sz[pv] += sz[pu];
   }
}
int solve(vector<int>& arr) {
   int n = arr.size() / 2;
   p = vector<int>(n);
   for (int i = 0; i < n; ++i)
   p[i] = i;
   sz = vector<int>(n, 1);
   for (int i = 0; i < n; ++i) {
      int u = arr[i << 1] / 2;
      int v = arr[i << 1 | 1] / 2;
      join(u, v);
   }
   int ans = 0;
   for (int i = 0; i < n; ++i)
   if (find(i) == i)
   ans += sz[i] − 1;
   return ans;
}
int main(){
   vector<int> v = {0, 5, 6, 2, 1, 3, 7, 4};
   cout << solve(v);
}

入力

{2, 4, 6, 3}

出力

23