1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ There are known lower bounds. It is impossible to simultaneously support union and find in constant time per operation. $\endgroup$
    – Steven
    Aug 19, 2022 at 22:41

1 Answer 1

0
$\begingroup$

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);
}
$\endgroup$
1
  • $\begingroup$ Ah yes, good catch! $\endgroup$
    – Vallerious
    Aug 19, 2022 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.