leetcodeSolution to some Leetcode problems written in C++ |
git clone git://git.dimitrijedobrota.com/leetcode.git |
Log | Files | Refs | README | LICENSE |
1361.cpp (1200B)
0 class UnionFind {
1 int n;
2 vector<int> root, rank;
4 public:
5 UnionFind(int n) : n(n), root(n), rank(n, 1) { iota(root.begin(), root.end(), 0); }
7 int find(int x) {
8 while (x != root[x])
9 x = root[x] = root[root[x]];
10 return x;
11 }
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 }
23 int count() { return n; }
24 };
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 }
36 public:
37 bool validateBinaryTreeNodes(int n, vector<int> &leftChild, vector<int> &rightChild) {
38 UnionFind uf(n);
39 vector<int> parent(n, -1);
41 for (int i = 0; i < n; i++)
42 if (!process(uf, parent, i, leftChild[i]) || !process(uf, parent, i, rightChild[i])) return false;
44 return uf.count() == 1;
45 }
46 };