0
Challenge · 56Graphs

Union-Find

Graphsused in ~70% of apps

A structure that answers one question extremely fast: are these two things in the same group? And it lets you merge groups as you go, which a traversal cannot do without starting over.

Core idea. Every item points at a parent. Follow the parents up and you reach a root, and the root is the name of the group. Two items are in the same group when they reach the same root. Merging two groups is one line: point one root at the other.
Playground, this isn't a screenshot
feed the edges in one at a time
leader of each node
0 follows 0
1 follows 1
2 follows 2
3 follows 3
4 follows 4
5 follows 5
groups left
6
everyone starts as their own leader, so there are six groups
step 1 of 7

The fourth edge joins two nodes that already share a leader. That is the cycle, spotted without a traversal.

↑ play a little first, then dig in