# 1722. Minimize Hamming Distance After Swap Operations
###### tags: `Leetcode` `Medium` `Union Find`
Link: https://leetcode.com/problems/minimize-hamming-distance-after-swap-operations/
## 思路
先union find找出source里面可以互换的index group
因此我们可以建一个group找到当前index可以换成的值有哪些(用map存)
接下来我们一个一个遍历source 看能否换成target对应的值
如果不行ans+1
如果可以就把这个值从map里面删掉 意味着之后不能再用了
## Code

class Solution {
    int[] fa;
    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int n = source.length;
        fa = new int[n];
        for(int i=0; i<n; i++) fa[i] = i;
        for(int[] allow:allowedSwaps) combine(allow[0], allow[1]);
        
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
        for(int i=0; i<n; i++){
            int f = find(i);
            if(!map.containsKey(f)) map.put(f, new HashMap<>());
            map.get(f).put(source[i], map.get(f).getOrDefault(source[i], 0)+1);
        }
        
        int ans = 0;
        for(int i=0; i<source.length; i++){
            int f = find(i);
            Map<Integer, Integer> temp = map.get(f);
            if(!temp.containsKey(target[i])) ans++;
            else{
                temp.put(target[i], temp.get(target[i])-1);
                if(temp.get(target[i])==0) temp.remove(target[i]);
            }
        }
        return ans;
    }
    private int find(int a){
        if(fa[a]==a) return a;
        return fa[a] = find(fa[a]);
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        fa[b] = a;
    }
}