leetcode

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

Union_Find.cpp (936B)

      1 class UnionFind {
      2     int n, cnt = n;
      3     mutable vector<int> root;
      4     vector<int> size;
      5 
      6   public:
      7     UnionFind(int n) : n(n), root(n), size(n, 1) { iota(root.begin(), root.end(), 0); }
      8     UnionFind(const UnionFind &uf) : n(uf.n), cnt(uf.cnt), root(uf.root), size(uf.size) {}
      9 
     10     int find(int x) const {
     11         while (x != root[x]) {
     12             x = root[x] = root[root[x]];
     13         }
     14         return x;
     15     }
     16 
     17     void join(int x, int y) {
     18         x = find(x), y = find(y);
     19         if (x == y) return;
     20 
     21         if (size[x] > size[y]) swap(x, y);
     22         root[x] = y;
     23         size[y] += size[x];
     24         cnt--;
     25     }
     26 
     27     void reset(int x) {
     28         root[x] = x;
     29         size[x] = 0;
     30     }
     31 
     32     void reset() {
     33         memset(size.data(), 0x00, size.size() * sizeof(int));
     34         iota(begin(root), end(root), 0);
     35     }
     36 
     37     int count() const { return cnt; }
     38     bool connected(int x, int y) const { return find(x) == find(y); }
     39 };