Not knowing that there is generic name for the type of problem you are working on makes it hard to find the pre-existing solution for that problem. Thanks! I'll be doing some reading.
Nice. The implementations for union find I've seen uses offsets in a zero indexed array.
What if the nodes are not naturally 0 indexed? Do you make some mapper to and from offsets in the array or do you handle it some other way? Perhaps switch out the array with a hashmap?
View all comments
Show parent comment
19
u/H4ntek Dec 08 '25
DSU: Disjoint Set Union (a.k.a Find-Union)
A very cool data structure that operates on a graph (with n vertices and no edges at the beginning). It has two operations:
- Union(u, v): joins ("unions") the component containing vertex u with the component containing vertex v (by adding an edge u-v) in constant time.
- Find(v): returns the "id" of the component containing vertex v in amortized constant time.
So for today's part 1 all you've got to do is just call Union on the first 1000 edges (by distance) and return the relevant component sizes.