leetcode

0 class UnionFind {

1 int n, cnt = n;

2 mutable vector<int> root;

3 vector<int> size;

4

5 public:

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

7 UnionFind(const UnionFind &uf) : n(uf.n), cnt(uf.cnt), root(uf.root), size(uf.size) {}

8

9 int find(int x) const {

10 while (x != root[x]) {

11 x = root[x] = root[root[x]];

12 }

13 return x;

14 }

15

16 void join(int x, int y) {

17 x = find(x), y = find(y);

18 if (x == y) return;

19

20 if (size[x] > size[y]) swap(x, y);

21 root[x] = y;

22 size[y] += size[x];

23 cnt--;

24 }

25

26 void reset(int x) {

27 root[x] = x;

28 size[x] = 0;

29 }

30

31 void reset() {

32 memset(size.data(), 0x00, size.size() * sizeof(int));

33 iota(begin(root), end(root), 0);

34 }

35

36 int count() const { return cnt; }

37 bool connected(int x, int y) const { return find(x) == find(y); }

38 };