C++で手をつないでいるカップル

N組のカップルが2N席に並んで座っていて、手を握りたいとします。すべてのカップルが並んで座っているように、スワップの最小数を見つける必要があります。

人と席は0から2N-1までの番号で表され、カップルは順番に番号が付けられます。これは、最初のカップルが（0、1）、2番目のカップルが（2、3）のようになります。最後のカップルは（2N-2、2N-1）です。

カップルの最初の座席は、rowと呼ばれる別の配列によって与えられ、row[i]は最初にi番目の座席に座っている人の値です。

したがって、入力が[0,2,4,1,3,5]の場合、出力は2

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

• UFと呼ばれるデータの1つのブロックを定義します。このブロックでは、いくつかのプロパティと関数を次のように定義します-

• 配列の親を定義する

• 値Nを取得してUFブロックを初期化し、次のようにします-

• カウント：=N

• 親：=サイズNの配列

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

  • 親[i]：=i

• 親[i]：=i

• parA：=getParent（a）

• parB：=getParent（b）

• parAがparBと同じ場合、-

  • 戻る

• （カウントを1つ減らします）

• parent [parB]：=parA

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

• parent [i]がiと同じ場合、-

  • iを返す

• return parent [i] =getParent（parent [i]）

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

• n：=行のサイズ、N：=n / 2

• ufというUFブロックを1つ作成し、N

  で初期化します。

• grを初期化する場合：=0、gr

  • a：=row [gr * 2]

  • b：=行[gr * 2 + 1]

  • ufのunionn（a / 2、b / 2）を呼び出す

• Nを返す-ufのカウント

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   class UF{
      public:
      vector<int> parent;
      int count;
      UF(int N){
         count = N;
         parent = vector<int>(N);
         for (int i = 0; i < N; i++) {
            parent[i] = i;
         }
      }
      void unionn(int a, int b){
         int parA = getParent(a);
         int parB = getParent(b);
         if (parA == parB)
         return;
         count--;
         parent[parB] = parA;
      }
      int getParent(int i){
         if (parent[i] == i)
         return i;
         return parent[i] = getParent(parent[i]);
      }
   };
   int minSwapsCouples(vector<int>& row) {
      int n = row.size();
      int N = n / 2;
      UF uf(N);
      for (int gr = 0; gr < N; gr++) {
         int a = row[gr * 2];
         int b = row[gr * 2 + 1];
         uf.unionn(a / 2, b / 2);
      }
      return N - uf.count;
   }
};
main(){
   Solution ob;
   vector<int> v = {0,2,4,1,3,5};
   cout << (ob.minSwapsCouples(v));
}

入力

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

出力

2