# Minimize Hamming Distance After Swap Operations

``````class Solution {
public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
int n = source.length;
DSU dsu = new DSU(n);
Map<Integer,HashMap<Integer, Integer>> map = new HashMap<>();
for(int[] a : allowedSwaps){
dsu.union(a[0], a[1]);
}
for(int i = 0 ; i < n; i++) {
int d = dsu.get(i);
map.putIfAbsent(d, new HashMap<Integer, Integer>());
map.get(d).putIfAbsent(source[i], 0);
map.get(d).put(source[i], map.get(d).get(source[i]) + 1);
}
int res = 0;
for(int i = 0; i < target.length; i++) {
int d = dsu.get(i);
if(!map.containsKey(d)){ // 如果dsu里没有坐标i (不能swap)
res++;
}
if(!map.get(d).containsKey(target[i])){ // 如果dsu有, 但是swap里没有target数组需要的
res++;
}
else{
map.get(dsu.get(i)).put(target[i], map.get(dsu.get(i)).get(target[i]) - 1); // 选了后减少
if(map.get(dsu.get(i)).get(target[i]) < 0)
res++;
}
}
return res;
}
private static class DSU {
private int[] ranks;
private int[] parents;
public DSU(int size) {
this.ranks = new int[size];
Arrays.fill(ranks, 1);
this.parents = new int[size];
for(int i = 0; i < size; i++){
this.parents[i]= i;
}
}

int get(int v) {
if (v == parents[v]) return v;
return parents[v] = get(parents[v]);
}

boolean union(int a, int b) {
a = get(a);
b = get(b);

if (a == b) return false;

if (ranks[a] < ranks[b]) {
int tmp = a;
a = b;
b = tmp;
}
parents[b] = a;
if (ranks[a] == ranks[b]) ++ranks[a];
return true;
}
}
}``````