在 c + + 中牵手的情侣

假设有N对夫妇，他们坐在连续排列的2N个座位上，想牵着手。我们必须找到交换的最小数量，以便每对夫妇并排坐着。

人员和座位由从0到2N-1的数字表示，对夫妇按顺序编号，例如第一对夫妇为(0,1)，第二对夫妇为(2,3)，依此类推，最后一对为(2N-2,2N-1)。

夫妇的初始座位由另一个称为row的数组给出，row [i]是最初坐在第i个座位的人的值。

因此，如果输入类似于[0,2,4,1,3,5]，则输出将为2

为了解决这个问题，我们将遵循以下步骤-

• 定义一个称为UF的数据块，在此块中定义一些属性和功能，如下所示-

• 定义一个父数组

• 通过取值N初始化UF块，然后执行以下操作-

• 数：= N

• parent：=大小为N的数组

• 对于初始化i：= 0，当i <N时，更新（将i增加1），执行-

• 父母[i]：=我

• 父母[i]：=我

• parA：= getParent(a)

• parB：= getParent(b)

• 如果parA与parB相同，则-

• 返回

• （将计数减少1）

• parent [parB]：= parA

• 定义一个函数getParent()，这需要我，

• 如果parent [i]与i相同，则-

• 还给我

• 返回parent [i] = getParent（parent [i]）

• 从主要方法中执行以下操作-

• n：=行的大小，N：= n / 2

• 创建一个名为uf的UF块并用N初始化

• 对于初始化gr：= 0，当gr <N时，更新（将gr增加1），执行-

• 一个：=行[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