package leetcode;

/**
 * https://leetcode.com/problems/number-of-operations-to-make-network-connected/
 */
public class Problem1319 {
    public int makeConnected(int n, int[][] connections) {
        // TODO
        return 0;
    }

    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
        System.out.println(prob.makeConnected(5, new int[][]{{0,1},{0,2},{3,4},{2,3}})); // 0
    }
}

@@ -12,16 +12,91 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.HashSet;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -274,15 +274,506 @@
     
-// TODO
+if (connections.length %3C n - 1) %7B%0A            return -1;%0A        %7D%0A        UnionFind uf = new UnionFind();%0A        for (int i = 0; i %3C connections.length; i++) %7B%0A            uf.union(connections%5Bi%5D%5B0%5D, connections%5Bi%5D%5B1%5D);%0A        %7D%0A        int answer = new HashSet%3C%3E(uf.map.values()).size() - 1; // number of connected computers%0A        // number of remaining computers%0A        for (int i = 0; i %3C n; i++) %7B%0A            if (!uf.map.containsKey(i)) %7B%0A               answer++;%0A            %7D%0A        %7D
 %0A   
@@ -784,17 +784,22 @@
  return 
-0
+answer
 ;%0A    %7D%0A
@@ -799,16 +799,698 @@
 %0A    %7D%0A%0A
+    private static class UnionFind %7B%0A        private final Map%3CInteger, Integer%3E map = new HashMap%3C%3E();%0A%0A        public 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            if (map.get(a).equals(map.get(b))) %7B%0A                return; // already connected%0A            %7D%0A            Integer value = map.get(a);%0A            for (Map.Entry%3CInteger, Integer%3E e : map.entrySet()) %7B%0A                if (e.getValue().equals(value)) %7B%0A                    map.put(e.getKey(), map.get(b));%0A                %7D%0A            %7D%0A        %7D%0A    %7D%0A%0A
     publ
@@ -1760,16 +1760,122 @@
 ); // 2%0A
+        System.out.println(prob.makeConnected(6, new int%5B%5D%5B%5D%7B%7B0,1%7D,%7B0,2%7D,%7B0,3%7D,%7B1,2%7D,%7B1,3%7D,%7B4,5%7D%7D)); // 1%0A
         

Update problem 1319