Path compression
While finding a root, point every node you pass straight at it, so the next find is a single step. About 10 minutes.
Remember the shortcut
The first time you walk to a friend's new flat, you follow every turn of the directions. After that, you know the shortcut.
Finding a leader can learn shortcuts too. Walk up the chain to find the leader as usual. Then walk the same path a second time and point every person on it straight at the leader. Next time, each of them reaches the leader in one step.
Finding 0's leader, first walk: follow the arrows up.
Use both tricks together
Small-under-big stops chains from growing long in the first place. Shortcuts flatten whatever chains exist as you use them. They solve different problems, and together they're the standard way to write union-find.
With both, even hundreds of thousands of merges and questions run comfortably inside the time limit.
parent[x] = parent[parent[x]] # skip a level
Finding a leader walks x, then y, then z, then the leader, and then takes the shortcuts. Who does y point to afterwards?
- AStraight to the leader
- BStill to z
Show the answer
Straight to the leader. Every person visited on the way, including y, now points straight at the leader.
Which team is X on?
There are n players, numbered 0 to n - 1, each starting on their own team. edges lists pairs [a, b] meaning a and b's teams merge, in order. After every merge, answer each pair in queries: return 1 if the two players in that query ended up on the same team, or 0 if not, in the same order as queries.
n = 4, edges = [[0, 1], [1, 2]], queries = [[0, 2], [0, 3]] → [1, 0]
1 ≤ n ≤ 100,000 · 0 ≤ edges.length ≤ 100,000 · 1 ≤ queries.length ≤ 100,000 · every pair has two different node numbers, each 0 ≤ x < n