假设我们有一个称为row的数字列表，它表示连续排的袜子。它们没有排序，但是我们要重新排列它们，以便每对袜子并排放置，例如(0,1)，(2,3)，(4,5)，依此类推。我们必须找到重新安排交换所需的最少数量。
因此，如果输入像row = [0，5，6，2，1，1，3，7，4]，则输出将为2，因为行顺序为
[0，5，6，2，1，1，3，7，4]
[0，1，6，2，5，5，3，7，4]
[0、1、3、2、5、6、7、4]
[0、1、3、2、5、4、7、6]
为了解决这个问题，我们将遵循以下步骤-
定义一个数组p和另一个数组sz
定义一个函数find()，它将花费你，
返回（如果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 <n时，更新（将i增加1），执行-
p [i]：= i
sz：=大小为n的数组，并用1填充
对于初始化i：= 0，当i <n时，更新（将i增加1），执行-
u：= arr [i / 2] / 2
v：= arr [（i / 2）OR 1] / 2
join(u, v)
回答：= 0
对于初始化i：= 0，当i <n时，更新（将i增加1），执行-
ans：= ans + sz [i] − 1
如果find(i)与i相同，则-
返回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