---
tags: Data Structure
title: Disjoint Sets
---

## 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](https://en.wikipedia.org/wiki/Ackermann_function#Inverse) (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;
};