Track which items belong to the same group, and merge two groups in nearly constant time.
Used for
parent[1] = 0
parent[3] = 2
leader(1) = 0, leader(3) = 2
leader(0) = 2 = leader(3)
Are 4 and 0 in the same group?
Not quite. Item 4 was never joined to anything, so it leads itself (4). The leader of 0 is 2. Different leaders mean different groups.
Step 1 of 6
Goal: keep track of which items belong to the same group, and merge groups quickly. Start with 5 separate groups. Each item points to a parent; an item that points to itself is the leader of its group.
Step 2 of 6
Join 0 and 1: make 0 the leader of 1.
Step 3 of 6
Join 2 and 3: make 2 the leader of 3.
Step 4 of 6
Join 1 and 3: follow the parents to find each leader. 1 leads to 0, and 3 leads to 2. Different leaders, so hang leader 0 under 2.
Step 5 of 6
Are 0 and 3 in the same group? Follow parents from each: both end at 2. Yes. Shortcuts that point items straight at their leader (path compression) keep these walks very short. This is union-find.
Step 6 of 6
Your turn.
const parent = [];const find = x => (parent[x] === undefined || parent[x] === x ? (parent[x] = x) : (parent[x] = find(parent[x])));const union = (a, b) => { parent[find(a)] = find(b); };