Union-Find, also called Disjoint Set Union (DSU), is used to manage groups of connected elements.

Its main operations are:

Find → Which group does this node belong to?
Union → Merge two groups.

The key advantage is:

DSU makes repeated connect + merge operations very fast.

Mental Trigger

“Are these connected?” + “Merge these groups” → DSU

Pattern Table

Pattern	What we need	Main change
Basic DSU	Merge groups	`union()`
Connectivity	Check same group	`connected()`
Path Compression	Faster `find()`	Compress parent
Union by Size	Balanced tree	Track `size[]`
Components	Count groups	Decrease count
Cycle Detection	Detect redundant edge	Check roots
Kruskal MST	Minimum connection cost	Sort edges + DSU

1. Generic DSU Template (Base)

This is the base template to understand first.

See components merge step by step — and why “same root?” is the cycle test Kruskal relies on:

Union-Find (Disjoint Set Union)

Maintain connected components and detect cycles with find/union.

find climbs parent[] to the root; union attaches one root under the other when they differ. Once two nodes share a root they're in the same component. This powers Kruskal's MST and cycle detection, with near-constant O(α(n)) per op via path compression/union by rank.

GRAPH VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        find(x): while parent[x] != x: x = parent[x]
                      
                        2
                        union(a, b):
                      
                        3
                          ra, rb = find(a), find(b)
                      
                        4
                          if ra == rb: return   // already same set
                      
                        5
                          parent[rb] = ra       // hang one root under other

class DSU {
    int[] parent;

    public DSU(int n) {
        parent = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        if (parent[x] == x) {
            return x;
        }

        return find(parent[x]);
    }

    public void union(int x, int y) {
        int px = find(x);
        int py = find(y);

        if (px != py) {
            parent[px] = py;
        }
    }
}

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] == x:
            return x

        return self.find(self.parent[x])

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)

        if px != py:
            self.parent[px] = py

struct DSU {
    vector<int> parent;

    DSU(int n) : parent(n) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] == x) {
            return x;
        }

        return find(parent[x]);
    }

    void unite(int x, int y) {
        int px = find(x);
        int py = find(y);

        if (px != py) {
            parent[px] = py;
        }
    }
};

class DSU {
  constructor(n) {
    this.parent = Array.from(
      { length: n },
      (_, i) => i
    );
  }

  find(x) {
    if (this.parent[x] === x) {
      return x;
    }

    return this.find(this.parent[x]);
  }

  union(x, y) {
    const px = this.find(x);
    const py = this.find(y);

    if (px !== py) {
      this.parent[px] = py;
    }
  }
}

How the base works

Initially:

0   1   2   3   4

Every node is its own group.

After:

union(0, 1);
union(1, 2);

we have:

0 ─ 1 ─ 2      3      4

So 0, 1, and 2 belong to the same group.

Two Operations to Remember

Find

find(x)

asks:

“Who is the root of x’s group?”

Union

union(x, y)

asks:

“Merge the groups containing x and y.”

DSU = Find the root + Merge the roots

Pattern 1: Connectivity Query

Problem Type

You need to answer:

“Are x and y connected?”

Code

public boolean connected(int x, int y) {
    return find(x) == find(y);
}

def connected(self, x, y):
    return self.find(x) == self.find(y)

bool connected(int x, int y) {
    return find(x) == find(y);
}

connected(x, y) {
  return this.find(x) === this.find(y);
}

What Changed from the Base?

Added a connectivity check

Base DSU already has:

find(x)
find(y)

We simply compare their roots:

find(x) == find(y)

If both have the same root:

same group → connected

Otherwise:

different groups → not connected

Connectivity = Compare the roots

Pattern 2: Path Compression

The basic find() works, but the tree can become deep.

For example:

1 → 2 → 3 → 4

Finding 1 requires walking through several nodes.

Path compression makes future searches faster.

Code

public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }

    return parent[x];
}

def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])

    return self.parent[x]

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }

    return parent[x];
}

find(x) {
  if (this.parent[x] !== x) {
    this.parent[x] = this.find(this.parent[x]);
  }

  return this.parent[x];
}

What Changed from the Base?

Before

return find(parent[x]);

After

parent[x] = find(parent[x]);

The important difference is:

We save the root directly inside parent[x].

Example

Before:

1 → 2 → 3 → 4

After finding 1:

1 → 4
2 → 3 → 4

Future find(1) becomes very fast.

Path Compression = point nodes directly toward their root

Pattern 3: Union by Size

Path compression makes find() faster.

We can also prevent the tree from becoming unnecessarily deep when merging.

We do this by keeping track of the size of each group.

Code

class DSU {
    int[] parent;
    int[] size;

    public DSU(int n) {
        parent = new int[n];
        size = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }

        return parent[x];
    }

    public void union(int x, int y) {
        int px = find(x);
        int py = find(y);

        if (px == py) {
            return;
        }

        if (size[px] < size[py]) {
            parent[px] = py;
            size[py] += size[px];
        } else {
            parent[py] = px;
            size[px] += size[py];
        }
    }
}

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])

        return self.parent[x]

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)

        if px == py:
            return

        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

struct DSU {
    vector<int> parent;
    vector<int> size;

    DSU(int n) : parent(n), size(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }

        return parent[x];
    }

    void unite(int x, int y) {
        int px = find(x);
        int py = find(y);

        if (px == py) {
            return;
        }

        if (size[px] < size[py]) {
            parent[px] = py;
            size[py] += size[px];
        } else {
            parent[py] = px;
            size[px] += size[py];
        }
    }
};

class DSU {
  constructor(n) {
    this.parent = Array.from(
      { length: n },
      (_, i) => i
    );
    this.size = new Array(n).fill(1);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }

    return this.parent[x];
  }

  union(x, y) {
    const px = this.find(x);
    const py = this.find(y);

    if (px === py) {
      return;
    }

    if (this.size[px] < this.size[py]) {
      this.parent[px] = py;
      this.size[py] += this.size[px];
    } else {
      this.parent[py] = px;
      this.size[px] += this.size[py];
    }
  }
}

What Changed from the Base?

1. Added `size[]`

int[] size;

This tells us how many nodes are in each group.

2. Changed the union rule

Base:

parent[px] = py;

Now:

if (size[px] < size[py]) {
    parent[px] = py;
} else {
    parent[py] = px;
}

We attach:

smaller group → larger group

This helps keep the tree shallow.

Union by Size = Attach the smaller tree under the bigger tree

Pattern 4: Count Connected Components

Problem Type

Find the number of groups after processing all edges.

For example:

0 — 1 — 2     3 — 4

There are:

2 components

Code

public int countComponents(int n, int[][] edges) {
    DSU dsu = new DSU(n);

    int components = n;

    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];

        if (dsu.find(u) != dsu.find(v)) {
            dsu.union(u, v);
            components--;
        }
    }

    return components;
}

def count_components(n, edges):
    dsu = DSU(n)

    components = n

    for u, v in edges:

        if dsu.find(u) != dsu.find(v):
            dsu.union(u, v)
            components -= 1

    return components

int countComponents(int n,
                    vector<vector<int>>& edges) {
    DSU dsu(n);

    int components = n;

    for (auto& edge : edges) {
        int u = edge[0];
        int v = edge[1];

        if (dsu.find(u) != dsu.find(v)) {
            dsu.unite(u, v);
            components--;
        }
    }

    return components;
}

function countComponents(n, edges) {
  const dsu = new DSU(n);

  let components = n;

  for (const [u, v] of edges) {
    if (dsu.find(u) !== dsu.find(v)) {
      dsu.union(u, v);
      components--;
    }
  }

  return components;
}

What Changed from the Base?

Added a component counter

Initially:

int components = n;

because every node starts as its own component.

Decrease when two groups merge

if (dsu.find(u) != dsu.find(v)) {
    dsu.union(u, v);
    components--;
}

If two different groups become one:

2 groups → 1 group

so:

components--;

Components = Start with n groups → subtract every successful merge

Pattern 5: Cycle Detection

DSU can detect cycles in an undirected graph.

Key Idea

Suppose we want to add:

u — v

If u and v are already connected:

find(u) == find(v)

then adding this edge creates a cycle.

Code

public boolean hasCycle(int n, int[][] edges) {
    DSU dsu = new DSU(n);

    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];

        if (dsu.find(u) == dsu.find(v)) {
            return true;
        }

        dsu.union(u, v);
    }

    return false;
}

def has_cycle(n, edges):
    dsu = DSU(n)

    for u, v in edges:

        if dsu.find(u) == dsu.find(v):
            return True

        dsu.union(u, v)

    return False

bool hasCycle(int n,
              vector<vector<int>>& edges) {
    DSU dsu(n);

    for (auto& edge : edges) {
        int u = edge[0];
        int v = edge[1];

        if (dsu.find(u) == dsu.find(v)) {
            return true;
        }

        dsu.unite(u, v);
    }

    return false;
}

function hasCycle(n, edges) {
  const dsu = new DSU(n);

  for (const [u, v] of edges) {
    if (dsu.find(u) === dsu.find(v)) {
      return true;
    }

    dsu.union(u, v);
  }

  return false;
}

What Changed from the Base?

Added a check before union

Base:

dsu.union(u, v);

Changed:

if (dsu.find(u) == dsu.find(v)) {
    return true;
}

Why?

Because:

If both nodes are already in the same group, this edge connects two nodes that already have a path between them.

That creates a cycle.

Cycle = Edge connects two nodes already in the same group

Pattern 6: Kruskal’s MST

Kruskal uses DSU to build a Minimum Spanning Tree.

The idea is simple:

Sort edges by weight.
Take the cheapest edge.
Skip it if it creates a cycle.
Otherwise, merge the two groups.

Code

public int kruskalMST(int n, int[][] edges) {

    Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));

    DSU dsu = new DSU(n);

    int cost = 0;
    int edgesUsed = 0;

    for (int[] edge : edges) {
        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];

        if (dsu.find(u) != dsu.find(v)) {

            dsu.union(u, v);

            cost += weight;
            edgesUsed++;

            if (edgesUsed == n - 1) {
                break;
            }
        }
    }

    return edgesUsed == n - 1 ? cost : -1;
}

def kruskal_mst(n, edges):
    edges.sort(key=lambda e: e[2])

    dsu = DSU(n)

    cost = 0
    edges_used = 0

    for u, v, weight in edges:

        if dsu.find(u) != dsu.find(v):

            dsu.union(u, v)

            cost += weight
            edges_used += 1

            if edges_used == n - 1:
                break

    return cost if edges_used == n - 1 else -1

int kruskalMST(int n,
               vector<vector<int>>& edges) {

    sort(edges.begin(), edges.end(),
         [](auto& a, auto& b) { return a[2] < b[2]; });

    DSU dsu(n);

    int cost = 0;
    int edgesUsed = 0;

    for (auto& edge : edges) {
        int u = edge[0];
        int v = edge[1];
        int weight = edge[2];

        if (dsu.find(u) != dsu.find(v)) {

            dsu.unite(u, v);

            cost += weight;
            edgesUsed++;

            if (edgesUsed == n - 1) {
                break;
            }
        }
    }

    return edgesUsed == n - 1 ? cost : -1;
}

function kruskalMST(n, edges) {
  edges.sort((a, b) => a[2] - b[2]);

  const dsu = new DSU(n);

  let cost = 0;
  let edgesUsed = 0;

  for (const [u, v, weight] of edges) {
    if (dsu.find(u) !== dsu.find(v)) {
      dsu.union(u, v);

      cost += weight;
      edgesUsed++;

      if (edgesUsed === n - 1) {
        break;
      }
    }
  }

  return edgesUsed === n - 1 ? cost : -1;
}

What Changed from the Base?

1. Sort edges

Added:

Arrays.sort(
    edges,
    (a, b) -> Integer.compare(a[2], b[2])
);

because Kruskal always considers the cheapest edges first.

2. Check for a cycle

Added:

if (dsu.find(u) != dsu.find(v))

We only accept an edge if it connects two different groups.

3. Track edges used

Added:

int edgesUsed = 0;

An MST with n vertices needs exactly:

n - 1 edges

Kruskal = Sort edges + DSU + Skip cycles

DSU Pattern Evolution

Base DSU
   ↓
Find root
   +
Union groups
   ↓
Connectivity
   (+ compare roots)
   ↓
Path Compression
   (+ save root)
   ↓
Union by Size
   (+ keep trees balanced)
   ↓
Components
   (+ count successful unions)
   ↓
Cycle Detection
   (+ check same root)
   ↓
Kruskal
   (+ sort edges by weight)

Common Mistakes

1. Forgetting `find()`

Wrong:

if (parent[x] == parent[y])

Correct:

if (find(x) == find(y))

parent[x] is not necessarily the final root.

2. Unioning nodes instead of roots

Wrong:

parent[x] = y;

Correct:

int px = find(x);
int py = find(y);

parent[px] = py;

Always merge roots.

3. Forgetting path compression

Basic DSU works, but optimized DSU should use:

parent[x] = find(parent[x]);

4. Using DSU cycle detection for directed graphs

This pattern is for:

Undirected graph cycle detection

Directed cycles are normally handled with DFS or topological sorting.

5. Forgetting to sort in Kruskal

Kruskal requires:

Arrays.sort(edges, ...);

before processing edges.

Recognition Cheat Sheet

If the problem says…	Think…
Are these nodes connected?	DSU
Merge two groups	DSU
Dynamic connectivity	DSU
Number of components	DSU
Redundant edge	DSU
Cycle in undirected graph	DSU
Minimum cost to connect all nodes	Kruskal + DSU
Edges arrive one by one	DSU

Earn Premium with Referrals

Mental Trigger

Pattern Table

1. Generic DSU Template (Base)

Union-Find (Disjoint Set Union)

How the base works

Two Operations to Remember

Find

Union

Pattern 1: Connectivity Query

Problem Type

Code

What Changed from the Base?

Added a connectivity check

Pattern 2: Path Compression

Code

What Changed from the Base?

Before

After

Example

Pattern 3: Union by Size

Code

What Changed from the Base?

1. Added size[]

2. Changed the union rule

Pattern 4: Count Connected Components

Problem Type

Code

What Changed from the Base?

Added a component counter

Decrease when two groups merge

Pattern 5: Cycle Detection

Key Idea

Code

What Changed from the Base?

Added a check before union

Pattern 6: Kruskal’s MST

Code

What Changed from the Base?

1. Sort edges

2. Check for a cycle

3. Track edges used

DSU Pattern Evolution

Common Mistakes

1. Forgetting find()

2. Unioning nodes instead of roots

3. Forgetting path compression

4. Using DSU cycle detection for directed graphs

5. Forgetting to sort in Kruskal

Recognition Cheat Sheet

Premium Content

My Private Notes

1. Added `size[]`

1. Forgetting `find()`