leetcode

0 class UnionFind {

1 vector<int> root, rank;

2 int n;

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 x = find(x), y = find(y);

15

16 if (x != y) {

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

18

19 root[x] = y;

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

21 }

22 }

23

24 int count() {

25 int cnt = 0;

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

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

28 return cnt;

29 }

30 };

31

32 class Solution {

33 public:

34 int findCircleNum(vector<vector<int>> &isConnected) {

35 int n = isConnected.size();

36 UnionFind uf(n);

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

38 for (int j = i + 1; j < n; j++)

39 if (isConnected[i][j]) uf.join(i, j);

40

41 return uf.count();

42 }

43 };