https://en.wikipedia.org/wiki/Disjoint-set_data_structure

It's a fairly simple algorithm to implement, but there is some wicked-cool analysis behind how fast it is.

It's a super good thing to have in your toolbox for any time you want to do any sort of "simultaneous flood-fill everywhere" or "partition everything" task.