Understand the disjoint set data structure (also called Union Find). It supports two operations: find determines which set an element belongs to (returning the root), union merges two sets into one by connecting their roots.
Path compression (flattening the tree during find) and union by rank (attaching smaller tree under larger) give near-constant amortized time. Know how to implement these. Union Find works well at dynamic connectivity queries.