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

15 if (x != y) {

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

17 root[x] = y;

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

19 n--;

20 }

21 }

22

23 int count() { return n; }

24 };

25

26 class Solution {

27 bool process(UnionFind &uf, vector<int> &parent, int start, int end) {

28 if (end == -1) return true;

29 if (parent[end] != -1) return false;

30 if (uf.find(start) == uf.find(end)) return false;

31 uf.join(start, end);

32 parent[end] = start;

33 return true;

34 }

35

36 public:

37 bool validateBinaryTreeNodes(int n, vector<int> &leftChild, vector<int> &rightChild) {

38 UnionFind uf(n);

39 vector<int> parent(n, -1);

40

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

42 if (!process(uf, parent, i, leftChild[i]) || !process(uf, parent, i, rightChild[i])) return false;

43

44 return uf.count() == 1;

45 }

46 };