Number of Operations to Make Network Connected LeetCode solution in C++

1
class Solution {
2
 public:
3
  // Union Find Approach
4

5
  vector<int> root;
6

7
  int find(int node) {
8
    if (root[node] != node) {
9
      return find(root[node]);
10
    }
11
    return node;
12
  }
13

14
  int makeConnected(int n, vector<vector<int>> &connections) {
15
    int m = connections.size();
16

17
    if (m < n - 1) {
18
      return -1;
19
    }
20

21
    for (int i = 0; i < n; i++) {
22
      root.push_back(i);
23
    }
24

25
    for (int i = 0; i < m; i++) {
26
      int v1 = connections[i][0];
27
      int v2 = connections[i][1];
28

29
      int r1 = find(v1);
30
      int r2 = find(v2);
31

32
      if (r1 != r2) {
33
        root[r1] = r2;
34
      }
35
    }
36

37
    int ans = 0;
38
    for (int i = 0; i < n; i++) {
39
      if (root[i] == i) {
40
        ans++;
41
      }
42
    }
43

44
    return ans - 1;
45
  }
46
};