package leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.com/problems/number-of-operations-to-make-network-connected/
 */
public class Problem1319 {
    public int makeConnected(int n, int[][] connections) {
        if (connections.length < n - 1) {
            return -1;
        }
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < connections.length; i++) {
            uf.union(connections[i][0], connections[i][1]);
        }
        int answer = 0;
        Set<Integer> connected = new HashSet<>(); // number of connected computers
        for (int i = 0; i < uf.map.length; i++) {
            if (uf.map[i] == null) {
                answer++; // number of remaining computers
            } else {
                connected.add(uf.map[i]);
            }
        }
        return answer + connected.size() - 1;
    }

    private static class UnionFind {
        private final Integer[] map;

        public UnionFind(int n) {
            this.map = new Integer[n];
        }

        public void union(int a, int b) {
            if (map[a] == null) {
                map[a] = a;
            }
            if (map[b] == null) {
                map[b] = b;
            }
            if (map[a].equals(map[b])) {
                return; // already connected
            }
            Integer value = map[a];
            for (int i = 0; i < map.length; i++) {
                if (map[i] == null) {
                    continue;
                }
                if (map[i].equals(value)) {
                    map[i] = map[b];
                }
            }
        }
    }

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

@@ -16,57 +16,8 @@
 e;%0A%0A
-import java.util.HashSet;%0Aimport java.util.Set;%0A%0A
 /**%0A
@@ -440,429 +440,121 @@
     
-int answer = 0;%0A        Set%3CInteger%3E connected = new HashSet%3C%3E(); // number of connected computers%0A        for (int i = 0; i %3C uf.map.length; i++) %7B%0A            if (uf.map%5Bi%5D == null) %7B%0A                answer++; // number of remaining computers%0A            %7D else %7B%0A                connected.add(uf.map%5Bi%5D);%0A            %7D%0A        %7D%0A        return answer + connected.size() - 1;%0A    %7D%0A%0A    private static class UnionFind %7B
+return uf.count - 1;%0A    %7D%0A%0A    public class UnionFind %7B%0A        private int%5B%5D parent; // parent%5Bi%5D = parent of i
 %0A   
@@ -570,27 +570,17 @@
 ate 
-f
 in
-al Integer%5B%5D map
+t count
 ;%0A%0A 
@@ -628,118 +628,90 @@
     
-this.map = new Integer%5Bn%5D;%0A        %7D%0A%0A        public void union(int a, int b) %7B%0A            if (map%5Ba%5D == null
+count = n;%0A            parent = new int%5Bn%5D;%0A            for (int i = 0; i %3C n; i++
 ) %7B%0A
@@ -730,18 +730,21 @@
     
-map%5Ba
+parent%5Bi
 %5D = 
-a
+i
 ;%0A  
@@ -767,447 +767,373 @@
     
-    if (map%5Bb%5D == null) %7B%0A                map%5Bb%5D = b;%0A            %7D%0A            if (map%5Ba%5D.equals(map%5Bb%5D)) %7B%0A                return; // already connected%0A            %7D%0A            Integer value = map%5Ba%5D;%0A            for (int i = 0; i %3C map.length; i++) %7B%0A                if (map%5Bi%5D == null) %7B%0A                    continue;%0A                %7D%0A                if (map%5Bi%5D.equals(value)) %7B%0A                    map%5Bi%5D = map%5Bb%5D;%0A                %7D
+%7D%0A%0A        public int root(int i) %7B%0A            while (i != parent%5Bi%5D) %7B%0A                i = parent%5Bi%5D;%0A            %7D%0A            return i;%0A        %7D%0A%0A        public void union(int a, int b) %7B%0A            int rootA = root(a);%0A            int rootB = root(b);%0A            if (rootA == rootB) %7B%0A                return;%0A            %7D%0A            parent%5BrootA%5D = rootB;
 %0A   
@@ -1133,33 +1133,40 @@
 tB;%0A            
-%7D
+count--;
 %0A        %7D%0A    %7D

Solve problem 1319