Problem: 1722. 执行交换操作后的最小汉明距离既然可以两两交换数字而且次数不限制所以可以任意排列首先并查集拿到所有可能的聚合体然后对每个根节点拿到这个树的所有索引i以及这个树的索引对应数值的统计值然后遍历每颗树对当前索引i若target[l[i]]在ump2内且值0则-1否则sum标记target[l[i]] -1最后统计不能交换且不同的个数Codeclass joinarr { public: vectorint arr; int n; joinarr(int n) { this-n n; arr.resize(n); for(int i 0; i n; i) arr[i] i; } int find(int a) { while(a!arr[a]) a arr[a]; return a; } void join(int a, int c) { int aa find(a); int cc find(c); if(aa cc) arr[cc] aa; else arr[aa] cc; } }; class Solution { public: int minimumHammingDistance(vectorint source, vectorint target, vectorvectorint allowedSwaps) { int n source.size(); int m allowedSwaps.size(); joinarr ja joinarr(n); for(int i 0; i m; i) { ja.join(allowedSwaps[i][0], allowedSwaps[i][1]); } unordered_mapint, vectorint ump; unordered_mapint, unordered_mapint, int ump2; int ind; for(int i 0; i n; i) { ind ja.find(i); ump[ind].push_back(i); ump2[ind][source[i]]; } int num, sum 0; for(auto [k, l] : ump) { for(int i 0; i l.size(); i) { num target[l[i]]; if(ump2[k].count(num) 0 ump2[k][num] 0) { ump2[k][num]--; } else { sum; } target[l[i]] -1; } } for(int i 0; i n; i) { if(target[i] 0 target[i] ! source[i]) { sum; } } return sum; } };