leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1361.cpp (1200B)

      1 class UnionFind {
      2     int n;
      3     vector<int> root, rank;
      4 
      5   public:
      6     UnionFind(int n) : n(n), root(n), rank(n, 1) { iota(root.begin(), root.end(), 0); }
      7 
      8     int find(int x) {
      9         while (x != root[x])
     10             x = root[x] = root[root[x]];
     11         return x;
     12     }
     13 
     14     void join(int x, int y) {
     15         x = find(x), y = find(y);
     16         if (x != y) {
     17             if (rank[x] > rank[y]) swap(x, y);
     18             root[x] = y;
     19             rank[y] += rank[x];
     20             n--;
     21         }
     22     }
     23 
     24     int count() { return n; }
     25 };
     26 
     27 class Solution {
     28     bool process(UnionFind &uf, vector<int> &parent, int start, int end) {
     29         if (end == -1) return true;
     30         if (parent[end] != -1) return false;
     31         if (uf.find(start) == uf.find(end)) return false;
     32         uf.join(start, end);
     33         parent[end] = start;
     34         return true;
     35     }
     36 
     37   public:
     38     bool validateBinaryTreeNodes(int n, vector<int> &leftChild, vector<int> &rightChild) {
     39         UnionFind uf(n);
     40         vector<int> parent(n, -1);
     41 
     42         for (int i = 0; i < n; i++)
     43             if (!process(uf, parent, i, leftChild[i]) || !process(uf, parent, i, rightChild[i])) return false;
     44 
     45         return uf.count() == 1;
     46     }
     47 };