1class Solution {
2    public int makeConnected(int n, int[][] connections) {
3        if (connections.length < n - 1) return -1;
4
5        int[] parent = new int[n];
6        int[] rank = new int[n];
7        for (int i = 0; i < n; ++i) parent[i] = i;
8
9        for (int[] conn : connections) {
10            union(parent, rank, conn[0], conn[1]);
11        }
12
13        int components = 0;
14        for (int i = 0; i < n; ++i) {
15            if (find(parent, i) == i) components++;
16        }
17
18        return components - 1;
19    }
20
21    private int find(int[] parent, int i) {
22        if (parent[i] != i) {
23            parent[i] = find(parent, parent[i]);
24        }
25        return parent[i];
26    }
27
28    private void union(int[] parent, int[] rank, int x, int y) {
29        int rootX = find(parent, x);
30        int rootY = find(parent, y);
31        if (rootX != rootY) {
32            if (rank[rootX] < rank[rootY])
33                parent[rootX] = rootY;
34            else if (rank[rootX] > rank[rootY])
35                parent[rootY] = rootX;
36            else {
37                parent[rootY] = rootX;
38                rank[rootX]++;
39            }
40        }
41    }
42}