1#include <stdio.h>
2#include <stdlib.h>
3
4int find(int* parent, int i) {
5    if (parent[i] == i)
6        return i;
7    return parent[i] = find(parent, parent[i]);
8}
9
10void union_sets(int* parent, int* rank, int x, int y) {
11    int rootX = find(parent, x);
12    int rootY = find(parent, y);
13    if (rootX != rootY) {
14        if (rank[rootX] < rank[rootY])
15            parent[rootX] = rootY;
16        else if (rank[rootX] > rank[rootY])
17            parent[rootY] = rootX;
18        else {
19            parent[rootY] = rootX;
20            rank[rootX]++;
21        }
22    }
23}
24
25int makeConnected(int n, int** connections, int connectionsSize, int* connectionsColSize) {
26    if (connectionsSize < n - 1)
27        return -1;
28
29    int* parent = (int*)malloc(n * sizeof(int));
30    int* rank = (int*)malloc(n * sizeof(int));
31    for (int i = 0; i < n; i++) {
32        parent[i] = i;
33        rank[i] = 0;
34    }
35
36    for (int i = 0; i < connectionsSize; i++) {
37        union_sets(parent, rank, connections[i][0], connections[i][1]);
38    }
39
40    int components = 0;
41    for (int i = 0; i < n; i++) {
42        if (find(parent, i) == i)
43            components++;
44    }
45
46    free(parent);
47    free(rank);
48
49    return components - 1;
50}