leetcode

0 class UnionFind {

1 int n;

2 vector<int> root, rank;

3

4 public:

5 UnionFind(int n) : n(n), root(n), rank(n, 1) { iota(root.begin(), root.end(), 0); }

6

7 int find(int x) {

8 while (x != root[x])

9 x = root[x] = root[root[x]];

10 return x;

11 }

12

13 void join(int x, int y) {

14 if (x != y) {

15 if (rank[x] > rank[y]) swap(x, y);

16

17 root[x] = y;

18 rank[y] += rank[x];

19 }

20 }

21

22 int count() {

23 int cnt = 0;

24 for (int i = 0; i < n; i++)

25 cnt += root[i] == i;

26 return cnt;

27 }

28 };

29

30 class Solution {

31 public:

32 int makeConnected(int n, vector<vector<int>> &connections) {

33 int count = 0;

34 UnionFind uf(n);

35 for (auto &edge : connections) {

36 int x = uf.find(edge[0]), y = uf.find(edge[1]);

37 if (x == y)

38 count++;

39 else

40 uf.join(x, y);

41 }

42 return count < uf.count() - 1 ? -1 : uf.count() - 1;

43 }

44 };