package leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * 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();
        for (int i = 0; i < connections.length; i++) {
            uf.union(connections[i][0], connections[i][1]);
        }
        int answer = new HashSet<>(uf.map.values()).size() - 1; // number of connected computers
        // number of remaining computers
        for (int i = 0; i < n; i++) {
            if (!uf.map.containsKey(i)) {
               answer++;
            }
        }
        return answer;
    }

    private static class UnionFind {
        private final Map<Integer, Integer> map = new HashMap<>();

        public void union(int a, int b) {
            if (!map.containsKey(a)) {
                map.put(a, a);
            }
            if (!map.containsKey(b)) {
                map.put(b, b);
            }
            if (map.get(a).equals(map.get(b))) {
                return; // already connected
            }
            Integer value = map.get(a);
            for (Map.Entry<Integer, Integer> e : map.entrySet()) {
                if (e.getValue().equals(value)) {
                    map.put(e.getKey(), map.get(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,34 +16,8 @@
 e;%0A%0A
-import java.util.HashMap;%0A
 impo
@@ -55,19 +55,19 @@
 va.util.
-Map
+Set
 ;%0A%0A/**%0A 
@@ -348,16 +348,17 @@
 ionFind(
+n
 );%0A     
@@ -502,49 +502,59 @@
 r = 
-new HashSet%3C%3E(uf.map.values()).size() - 1
+0;%0A        Set%3CInteger%3E connected = new HashSet%3C%3E()
 ; //
@@ -588,49 +588,8 @@
 ers%0A
-        // number of remaining computers%0A
     
@@ -612,17 +612,29 @@
  0; i %3C 
-n
+uf.map.length
 ; i++) %7B
@@ -654,34 +654,30 @@
 if (
-!
 uf.map
-.containsKey(i)
+%5Bi%5D == null
 ) %7B%0A
+ 
     
@@ -696,16 +696,112 @@
 nswer++;
+ // number of remaining computers%0A            %7D else %7B%0A                connected.add(uf.map%5Bi%5D);
 %0A       
@@ -838,16 +838,39 @@
 n answer
+ + connected.size() - 1
 ;%0A    %7D%0A
@@ -933,52 +933,106 @@
 nal 
-Map%3C
 Integer
-, Integer%3E map = new HashMap%3C%3E();
+%5B%5D map;%0A%0A        public UnionFind(int n) %7B%0A            this.map = new Integer%5Bn%5D;%0A        %7D
 %0A%0A  
@@ -1091,27 +1091,22 @@
 if (
-!
 map
-.containsKey(a)
+%5Ba%5D == null
 ) %7B%0A
@@ -1128,18 +1128,15 @@
  map
-.put(a,
+%5Ba%5D =
  a
-)
 ;%0A  
@@ -1167,27 +1167,22 @@
 if (
-!
 map
-.containsKey(b)
+%5Bb%5D == null
 ) %7B%0A
@@ -1204,18 +1204,15 @@
  map
-.put(b,
+%5Bb%5D =
  b
-)
 ;%0A  
@@ -1242,23 +1242,19 @@
  if (map
-.get(a)
+%5Ba%5D
 .equals(
@@ -1256,23 +1256,19 @@
 uals(map
-.get(b)
+%5Bb%5D
 )) %7B%0A   
@@ -1358,15 +1358,11 @@
  map
-.get(a)
+%5Ba%5D
 ;%0A  
@@ -1380,54 +1380,38 @@
 or (
-Map.Entry%3CInteger, Integer%3E e :
+int i = 0; i %3C
  map.
+l
 en
-trySet()
+gth; i++
 ) %7B%0A
@@ -1434,20 +1434,100 @@
 if (
-e.getValue()
+map%5Bi%5D == null) %7B%0A                    continue;%0A                %7D%0A                if (map%5Bi%5D
 .equ
@@ -1567,36 +1567,20 @@
  map
-.put(e.getKey(), map.get(b))
+%5Bi%5D = map%5Bb%5D
 ;%0A  

Update problem 1319