Motivation

Design a data structure that stores a partition of a set.
With the operations of union, find, etc.

Naive

Way-A: Update the Set Each Element Belongs to

• Find:
  $O(1)$
• Make Union:
  $O(N)$

Way-B: Update the Relation Between Elements

• Find:
  $O(N)$
• Make Union:
  $O(1)$

Disjoint Sets (Union-find)

Concept

If two elements are in the same set, then the head of both are the same.

Meaning of Values

If djs[x] is negative, then x is the head of the set,
and -djs[x] is the population of the set.

Otherwise, djs[x] is also a member(it's usually head) of the set.

Find

If djs[x] is negative, then x is the head of the set.
Otherwise, replace djs[x] with find(djs[x]). (Path compression)

Make Union

Compare djs[find(x)] with djs[find(y)],
adding the smaller set to the other one. (Union by Rank)

Complexity

• Initiallization:
  $O(N)$
• Each Operation:
  $O(\alpha (N)),\alpha :$ Inverse Ackermann Function (nearly constant, with path compression and union by rank)
• Space:
  $O(N)$

Sample Code

class DisjointSets {
    DisjointSets(int n) : djs(n, -1) {}
    
    int find(int x) {
        if (djs[x] < 0) return x;
        return djs[x] = find(djs[x]); // Path Compression
    }
    
    int population(int x) {
        return -djs[find(x)];
    }
    
    void unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        
        // Union By Rank
        if (djs[px] < djs[py]) { // population: x > y
            djs[px] += djs[py];
            djs[py] = px;
        }
        else {
            djs[py] += djs[px];
            djs[px] = py;
        }
    }
    
private:
    vector<int> djs;
};