package leetcode;

/**
 * https://leetcode.com/problems/min-cost-to-connect-all-points/
 */
public class Problem1584 {
    public int minCostConnectPoints(int[][] points) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem1584 prob = new Problem1584();
        System.out.println(prob.minCostConnectPoints(new int[][]{
            {0,0},{2,2},{3,10},{5,2},{7,0}
        })); // 20
        System.out.println(prob.minCostConnectPoints(new int[][]{
            {3,12},{-2,5},{-4,1}
        })); // 18
        System.out.println(prob.minCostConnectPoints(new int[][]{
            {0,0},{1,1},{1,0},{-1,1}
        })); // 4
        System.out.println(prob.minCostConnectPoints(new int[][]{
            {-1000000,-1000000},{1000000,1000000}
        })); // 4000000
        System.out.println(prob.minCostConnectPoints(new int[][]{
            {0,0}
        })); // 0
    }
}

@@ -12,16 +12,78 @@
 tcode;%0A%0A
+import java.util.Comparator;%0Aimport java.util.PriorityQueue;%0A%0A
 /**%0A * h
@@ -240,740 +240,1844 @@
     
-// TODO%0A        return 0
+PriorityQueue%3CEdge%3E queue = new PriorityQueue%3C%3E(Comparator.comparingInt(a -%3E a.distance))
 ;%0A    
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem1584 prob = new Problem1584();%0A        System.out.println(prob.minCostConnectPoints(new int%5B%5D%5B%5D%7B%0A            %7B0,0%7D,%7B2,2%7D,%7B3,10%7D,%7B5,2%7D,%7B7,0%7D%0A        %7D)); // 20%0A        System.out.println(prob.minCostConnectPoints(new int%5B%5D%5B%5D%7B%0A            %7B3,12%7D,%7B-2,5%7D,%7B-4,1%7D%0A        %7D)); // 18
+for (int i = 0; i %3C points.length; i++) %7B%0A            for (int j = i + 1; j %3C points.length; j++) %7B%0A                int distance =%0A                    Math.abs(points%5Bi%5D%5B0%5D - points%5Bj%5D%5B0%5D) + Math.abs(points%5Bi%5D%5B1%5D - points%5Bj%5D%5B1%5D);%0A                queue.add(new Edge(i, j, distance));%0A            %7D%0A        %7D%0A        int answer = 0;%0A        UnionFind uf = new UnionFind();%0A        while (!queue.isEmpty()) %7B%0A            Edge edge = queue.poll();%0A            if (!uf.connected(edge.from, edge.to)) %7B%0A                uf.union(edge.from, edge.to);%0A                answer += edge.distance;%0A            %7D%0A        %7D%0A        return answer;
 %0A    
+%7D%0A%0A
     
-System.out.println(prob.minCostConnectPoints(new int%5B%5D%5B%5D%7B%0A            %7B0,0%7D,%7B1,1%7D,%7B1,0%7D,%7B-1,1%7D%0A        %7D)); // 4%0A        System.out.println(prob.minCostConnectPoints(new int%5B%5D%5B%5D%7B%0A            %7B-1000000,-1000000%7D,%7B1000000,1000000%7D%0A        %7D)); // 4000000%0A        System.out.println(prob.minCostConnectPoints(new int%5B%5D%5B%5D%7B%0A            %7B0,0%7D%0A        %7D)); // 0
+private static class Edge %7B%0A        private final int from;%0A        private final int to;%0A        private final int distance;%0A%0A        Edge(int from, int to, int distance) %7B%0A            this.from = from;%0A            this.to = to;%0A            this.distance = distance;%0A        %7D%0A    %7D%0A%0A    private static class UnionFind %7B%0A        private final Integer%5B%5D map = new Integer%5B1000%5D;%0A%0A        void union(int a, int b) %7B%0A            if (map%5Ba%5D == null) %7B%0A                map%5Ba%5D = a;%0A            %7D%0A            if (map%5Bb%5D == null) %7B%0A                map%5Bb%5D = b;%0A            %7D%0A            if (!connected(a, b)) %7B%0A                return;%0A            %7D%0A            int value = map%5Ba%5D;%0A            for (int i = 0; i %3C map.length; i++) %7B%0A                if (map%5Bi%5D != null) %7B%0A                    if (map%5Bi%5D == value) %7B%0A                        map%5Bi%5D = map%5Bb%5D;%0A                    %7D%0A                %7D%0A            %7D%0A        %7D%0A%0A        boolean connected(int a, int b) %7B%0A            if (map%5Ba%5D == null %7C%7C map%5Bb%5D == null) %7B%0A                return false;%0A            %7D%0A            return map%5Ba%5D == map%5Bb%5D;%0A        %7D
 %0A   

Solve problem 1584