在 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