Disjoint Set Constant Time Union Operation

Question

I am following a LeetCode tutorial for Disjoint sets I have trouble understanding why the so called "Quick Find" method needs to take O(n) time. I have implemented an data structure that has an optimised Union operation and it is O(1).

// Base class for all types of disjoint sets.
class DisjointSet {
public:
  DisjointSet(int n) : _n(n), vertices(new int[n]) {
    for (int i = 0; i < n; i++) {
      vertices[i] = i;
    }
  }

  /* Finds the root node of a given vertex */
  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);
  }
protected:
  int _n;
  int* vertices;
};

And the concrete implementation:

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

    int find(int vertex) const {
      while (vertices[vertex] != vertex) {
        vertex = vertices[vertex];
      }

      return vertex;
    }

    void union_(int v1, int v2) const {
      vertices[v2] = v1;
    }
  };

The idea is that we are keeping track of each vertex's parent and when finding we are going 'up' until we have a vertex whos parent is itself. For the union operation we are just changing the parent of the second node and the find will work because it is going one parent at a time.

Why do we need to check for the rank and whether the roots are the same in the official implementation? I fail to see the logic discrepancy in my approach.

Answer 1

Unfortunately, your implementation of disjoint sets does not work.

For example, consider the following calling sequence.

s = FastUnionSlowFindSet(3);

s.union_(0,1);
s.union_(2,1);

After two union operations, all three vertices 0, 1, 2 should be in the same set.

However, the only relation we have is vertices[1] = 2, as it has overwritten vertices[1] = 0. So s contains two disjoint sets, {1, 2} and {0}.

---

To avoid such a bug, it is necessary to implement union_ as something like the following.

void union_(int v1, int v2) const {
    vertices[find(v2)] = find(v1);
}