程序查找在C ++中将所有袜子组合在一起所需的最少交换次数
假设我们有一个称为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）OR1]/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