Java || Union-Find || beats 100% || 2ms
\n    // O(n+connections.length)\n    public int makeConnected(int n, int[][] connections) {\n\n\t\tif (connections.length < n - 1)\n\t\t\treturn -1;\n\n\t\tint
\n    // O(n+connections.length)\n    public int makeConnected(int n, int[][] connections) {\n\n\t\tif (connections.length < n - 1)\n\t\t\treturn -1;\n\n\t\tint[] rank = new int[n];\n\t\tint[] parent = new int[n];\n\n\t\tfor (int i = 0; i < n; i++)\n\t\t\tparent[i] = i;\n\n\t\tint groups = n;\n\n\t\tfor (int[] connection : connections) {\n\t\t\tint u = connection[0];\n\t\t\tint v = connection[1];\n\t\t\tboolean flag = union(parent, rank, u, v);\n\t\t\tif (flag)\n\t\t\t\tgroups--;\n\t\t}\n\n\t\treturn groups - 1;\n\t}\n\n\t// O(1)\n\tpublic static int find(int[] parent, int x) {\n\n\t\tif (parent[x] == x)\n\t\t\treturn x;\n\n\t\tint temp = find(parent, parent[x]);\n\t\tparent[x] = temp;\n\t\treturn temp;\n\t}\n\n\t// O(1)\n\tpublic static boolean union(int[] parent, int[] rank, int x, int y) {\n\n\t\tint parentx = find(parent, x);\n\t\tint parenty = find(parent, y);\n\n\t\tif (parentx == parenty)\n\t\t\treturn false;\n\n\t\tint rankx = rank[parentx];\n\t\tint ranky = rank[parenty];\n\n\t\tif (rankx < ranky)\n\t\t\tparent[parentx] = parenty;\n\t\telse if (rankx > ranky)\n\t\t\tparent[parenty] = parentx;\n\t\telse {\n\t\t\tparent[parentx] = parenty;\n\t\t\trank[parenty]++;\n\t\t}\n\t\treturn true;\n\t}\n
[]