Skip to content
Back to Data StructuresAll lessons

Data Structures

Union-Find (Disjoint Set)

find and union: O(α(n)) each. α is the inverse Ackermann function, a number that stays under 5. In practice, this is effectively constant time, thanks to path compression.

The idea, in plain English

Union-Find is like tracking friend groups at a party. Everyone starts alone, in their own tiny group. When two people become friends, their two whole groups merge into one. To check 'are these two in the same group?', you don't list every member. You just look up each person's group leader and see if the leaders match.

How it works

  1. 1find(x): follow x's 'leader' pointer up the chain, until you reach someone who is their own leader. That person represents the group.
  2. 2While you follow that chain, point every node straight at the final leader. This is called path compression, and it makes the next find instant.
  3. 3union(a, b): find both leaders. If they differ, make one leader point to the other, so the two groups become one.
  4. 4connected(a, b): this is true only when find(a) and find(b) land on the same leader.

When you'd use it

Use Union-Find to detect cycles in a graph, build a minimum spanning tree with Kruskal's algorithm, or group things into 'friend circles.' It fits anything that keeps asking 'are these two already connected?' while you add connections over time.

Common beginner mistakes

  • Don't skip path compression or union by rank/size. Without one of these, chains can grow long, and every find slows toward O(n).
  • If you call union on two items already in the same group, nothing happens. This is correct behavior, not a bug.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
0 and 2 connected: yes
0 and 3 connected: no
0 and 3 connected: yes
5 and 0 connected: no

See it in motion

Merge the groupsUnion-Findfind and union: O(α(n)) each. α is the inverse Ackermann function, a number that stays under 5. In practice, this is effectively constant time, thanks to path compression.
0leader1leader2leader3leader4leader5leader

6 elements, each alone in its own set — every element is its own leader.

6
Sets
start
Operation
1/25
Step
0.0s
Time
Active in opSet ASet BOwn set

Not sure this is the right topic? See the learning paths → or where this leads →