Union-find

[stevelinton]

One for the todo list -- Union-find data structures are less well known than they should be, but amazingly useful. They model partitions of a finite set. The key operations are "find the canonical representative of the component containing a given element" and "unite these two components into one bigger component". Both can be done in time amortized time proportional to the inverse ackerman function of the size of the set (ie as near constant as makes no difference). Algorithms are simple.