leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1361.cpp (1200B)

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 };