Interview OS
Back to Algorithms & Data Structures

Library

Union-Find (DSU)

Near-O(1) connectivity.

Graph

Overview

Union-Find (disjoint set) tracks which elements belong to the same group and merges groups in near-constant time using path compression and union by rank. It's the backbone of connectivity and Kruskal's MST.

How it works

Graph
InitUnionFindOutputOwn setparent[i]=iMerge setsunionRoot≈O(1)Use
ClientServiceDataEdge

Step by step, with examples

  1. 1

    Own set

    • Each element's parent is itself.
  2. 2

    Merge sets

    • Link roots by rank/size.
  3. 3

    Root

    • Path compression flattens the tree.
  4. 4

    Use

    • Connectivity and Kruskal's MST.
    • Example: cycle detect

Overview

Disjoint-set union with path compression + union by rank gives near-constant amortized operations.

When to use it

  • Connected components
  • Kruskal's MST
  • Cycle detection in undirected graphs

Reference

function find(p,x){ while(p[x]!==x){ p[x]=p[p[x]]; x=p[x]; } return x; }

Common pitfalls

  • Skipping path compression
  • Union by size vs rank mistakes

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides