union-find
Union-find, also called a disjoint-set data structure, tracks a collection of items partitioned into groups, and answers one question fast: are these two items in the same group? It supports two operations: find (which group does this item belong to?) and union (merge the two groups containing these items). Picture friend circles — union-find can instantly tell you whether two people are already in the same circle, and merge two circles into one.
Each group is stored as a tree where every item points to a parent, and the root of the tree is the group's representative. find walks up to the root; union links one root under another. Done naively the trees can grow tall and slow, so two optimizations are applied together. Path compression flattens the tree during find by pointing visited items straight at the root. Union by rank (or size) always attaches the shorter tree under the taller one, keeping trees shallow.
With both optimizations, the amortized cost per operation is effectively constant — formally O(alpha(n)), where alpha is the inverse Ackermann function, which is at most about 4 for any input you will ever see. This near-O(1) speed makes union-find the engine inside Kruskal's algorithm, where it checks in constant time whether adding an edge would form a cycle, and a staple for connectivity and grouping problems generally.
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]); // path compression
return parent[x];
}
void unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return;
if (rank_[a] < rank_[b]) swap(a, b);
parent[b] = a;
if (rank_[a] == rank_[b]) ++rank_[a];
}find points each visited node straight at the root; union hangs the shorter tree under the taller.
alpha(n), the inverse Ackermann function, grows so slowly it is below 5 for any practical n, so people often just call union-find 'effectively O(1) per operation.'