leetcode

Solution to some Leetcode problems written in C++

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

Union_Find.cpp (936B)

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