Union-Find

Union-find tracks disjoint groups while they keep merging, and answers "are these two in the same group?" Each element points at a parent, the root of each tree names its group, and a union just hangs one root under the other.

Field	C++	Python	Java
Parent of each element	vector<int>	list	int[]
Size of each root's group	vector<int>	list	int[]
Groups remaining	int	int	int

No standard library ships one, and the naive version can degrade to a linked list. Without path compression and union by size, a bad merge order builds a chain of depth $n$ where every find costs $O(n)$. Path compression points every visited node straight at the root on the way up, and union by size hangs the smaller tree under the larger one, making each operation nearly constant. Because union-find only merges and never splits, a problem that deletes edges has to process its events in reverse or use a graph traversal instead.

Operation	Naive parent links	Compression + union by size
Find a root	$O(n)$	$O(\alpha(n))$
Merge two groups	$O(n)$	$O(\alpha(n))$
Same group?	$O(n)$	$O(\alpha(n))$

Use it when edges or equivalences arrive one at a time and you keep asking how many groups there are, whether two things are connected, or what a whole group adds up to.

The problems below start with counting components, move through asking about one component and totalling every component, and end with Kruskal's minimum spanning tree.