DisjointSet.cpp

#include <iostream>
#include <vector>
#include <future>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/* A DS for finding the root node of a vertex in a tree. 
!Does not keep track of the original tree structure so it cannot be reconstructed exactly. */
class DisjointSet {
public:
  DisjointSet(int n) : _n(n), vertices(new int[n]) {
    for (int i = 0; i < n; i++) {
      vertices[i] = i;
    }
  }
  virtual ~DisjointSet() {
    delete[] vertices;
  }

  virtual int find(int vertex) const = 0;

  virtual void union_(int vertex1, int vertex2) const = 0;

  bool connected(int v1, int v2) const {
    return find(v1) == find(v2);
  }

  virtual void print() const {
    for (int i = 0; i < _n; i++) {
      cout << vertices[i] << " ";
    }
    cout << endl;
  }
protected:
  int _n;
  int* vertices;
};

class FastFindSlowUnionSet : public DisjointSet {
public:
  FastFindSlowUnionSet(int n) : DisjointSet(n) {}

  /* O(1) */
  int find(int vertex) const {
    return vertices[vertex];
  }

  /* O(n) */
  void union_(int vertex1, int vertex2) const {
    int vertex1Root = vertices[vertex1];
    int vertex2Root = vertices[vertex2];

    if (vertex1Root == vertex2Root) {
      return;
    }
    
    vertices[vertex2] = vertex1Root;

    for (int i = 0; i < _n; i++) {
      if (vertices[i] == vertex2) {
        vertices[i] = vertex1Root;
      }
    }
  }
};

class FastUnionSlowFindSet : public DisjointSet {
public:
  FastUnionSlowFindSet(int n) : DisjointSet(n) {
    rank = new int[n];
    for (int i = 0; i < n; i++) {
      rank[i] = 1;
    }
  }

  ~FastUnionSlowFindSet() {
    delete[] rank;
  }

  int find(int vertex) const {
    if (vertices[vertex] == vertex) {
      return vertex;
    }
    int root = find(vertices[vertex]);

    vertices[vertex] = root;

    return root;
  }

  void union_(int v1, int v2) const {
    int v1Root = find(v1);
    int v2Root = find(v2);

    if (v1Root == v2Root) {
      return;
    }

    if (rank[v1Root] > rank[v2Root]) {
      vertices[v2Root] = v1Root;
    }
    else if (rank[v1Root] < rank[v2Root]) {
      vertices[v1Root] = v2Root;
    }
    else {
      vertices[v2Root] = v1Root;
      rank[v2Root] += 1;
    }
  }

  void print() const override {
    cout << "Vertices: " << endl;
    DisjointSet::print();

    cout << "Rank: " << endl;
    for (int i = 0; i < _n; i++) {
      cout << rank[i] << " ";
    }
    cout << endl;
  }

private:
  int* rank;
};

int main() {
  DisjointSet* disi = new FastUnionSlowFindSet(10);

  disi->union_(1, 2);
  disi->print();
  disi->union_(2, 5);
  disi->print();
  disi->union_(5, 6);
  disi->print();
  disi->union_(6, 7);
  disi->print();
  disi->union_(3, 8);
  disi->union_(8, 9);

  disi->print();

  cout << disi->connected(7, 1) << endl;
}