package leetcode;

/**
 * https://leetcode.com/problems/minimize-hamming-distance-after-swap-operations/
 */
public class Problem1722 {
    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem1722 prob = new Problem1722();
        System.out.println(prob.minimumHammingDistance(
            new int[]{1,2,3,4}, new int[]{2,1,4,5}, new int[][]{{0,1},{2,3}})); // 1
        System.out.println(prob.minimumHammingDistance(
            new int[]{1,2,3,4}, new int[]{1,3,2,4}, new int[][]{})); // 2
        System.out.println(prob.minimumHammingDistance(
            new int[]{5,1,2,4,3}, new int[]{1,5,4,2,3}, new int[][]{{0,4},{4,2},{1,3},{1,4}})); // 0
        System.out.println(prob.minimumHammingDistance(
            new int[]{5,1,2,4,3}, new int[]{1,5,4,2,3}, new int[][]{{0,3},{3,2},{3,1}})); // 0
        System.out.println(prob.minimumHammingDistance(
            new int[]{5,1,2,4,3}, new int[]{1,5,4,2,4}, new int[][]{{0,3},{3,2},{3,1}})); // 1
    }
}

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -280,33 +280,1271 @@
     
-// TODO%0A        return 0;
+UnionFind uf = new UnionFind();%0A        for (int%5B%5D pair : allowedSwaps) %7B%0A            uf.union(source%5Bpair%5B0%5D%5D, source%5Bpair%5B1%5D%5D);%0A        %7D%0A        int answer = 0;%0A        for (int i = 0; i %3C source.length; i++) %7B%0A            if (source%5Bi%5D != target%5Bi%5D && !uf.connected(source%5Bi%5D, target%5Bi%5D)) %7B%0A                answer++;%0A            %7D%0A        %7D%0A        return answer;%0A    %7D%0A%0A    private static class UnionFind %7B%0A        private final Map%3C/* child */ Integer, /* parent */ Integer%3E map = new HashMap%3C%3E();%0A%0A        private void union(int a, int b) %7B%0A            if (!map.containsKey(a)) %7B%0A                map.put(a, a);%0A            %7D%0A            if (!map.containsKey(b)) %7B%0A                map.put(b, b);%0A            %7D%0A            int x = find(a);%0A            int y = find(b);%0A            if (x != y) %7B%0A                map.put(x, y);%0A            %7D%0A        %7D%0A%0A        private Integer find(int a) %7B%0A            int child = a;%0A            int parent = map.get(a);%0A            while (child != parent) %7B%0A                child = parent;%0A                parent = map.get(child);%0A            %7D%0A            return parent;%0A        %7D%0A%0A        private boolean connected(int a, int b) %7B%0A            return map.containsKey(a) && map.containsKey(b) && find(a) == find(b);%0A        %7D
 %0A   
@@ -1634,24 +1634,26 @@
 blem1722();%0A
+//
         Syst
@@ -1688,32 +1688,34 @@
 ammingDistance(%0A
+//
             new 
@@ -1779,24 +1779,26 @@
 3%7D%7D)); // 1%0A
+//
         Syst
@@ -1833,32 +1833,34 @@
 ammingDistance(%0A
+//
             new 
@@ -1917,16 +1917,18 @@
 ); // 2%0A
+//
         
@@ -1967,32 +1967,34 @@
 ammingDistance(%0A
+//
             new 
@@ -2070,32 +2070,34 @@
 ,%7B1,4%7D%7D)); // 0%0A
+//
         System.o
@@ -2128,32 +2128,34 @@
 ammingDistance(%0A
+//
             new 
@@ -2233,16 +2233,18 @@
 ); // 0%0A
+//
         
@@ -2291,16 +2291,18 @@
 stance(%0A
+//
         
@@ -2388,16 +2388,153 @@
 ); // 1%0A
+        System.out.println(prob.minimumHammingDistance(%0A            new int%5B%5D%7B2,3,1%7D, new int%5B%5D%7B1,2,2%7D, new int%5B%5D%5B%5D%7B%7B0,2%7D,%7B1,2%7D%7D)); // 1%0A
     %7D%0A%7D%0A

Update problem 1722