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.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
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