leetcode

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

0990.cpp (814B)

      1 class UnionFind {
      2     vector<int> root, rank;
      3 
      4   public:
      5     UnionFind(int n) : root(n), rank(n, 1) { iota(root.begin(), root.end(), 0); }
      6 
      7     int find(int x) {
      8         if (x == root[x]) return x;
      9         return root[x] = find(root[x]);
     10     }
     11 
     12     void join(int x, int y) {
     13         x = find(x), y = find(y);
     14 
     15         if (x != y) {
     16             if (rank[x] > rank[y]) swap(x, y);
     17             root[y] = x;
     18             rank[x] += x == y;
     19         }
     20     }
     21 };
     22 
     23 class Solution {
     24   public:
     25     bool equationsPossible(vector<string> &equations) {
     26         UnionFind uf(26);
     27         for (auto &s : equations)
     28             if (s[1] == '=') uf.join(s[0] - 'a', s[3] - 'a');
     29 
     30         for (auto &s : equations)
     31             if (s[1] == '!' && uf.find(s[0] - 'a') == uf.find(s[3] - 'a')) return false;
     32         return true;
     33     }
     34 };