Which things are connected

A structure with two operations: are these two in the same group, and merge these two groups. Both effectively constant time.

It is the right answer whenever the question is about connectivity and there is no need to know the actual path.

The idea

Each element points at a parent. The root of the chain identifies the group. Two elements are in the same group when they have the same root.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))     # everyone their own group
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path compression
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                 # already together
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra             # union by rank
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

The two optimisations

Without them, a chain of unions builds a linked list and find becomes O(n).

Union by rank attaches the shorter tree under the taller one, so the height grows slowly.

Path compression points every node visited during a find straight at the root, so the next lookup is immediate. The line doing it is the one assignment inside the loop.

Together the amortised cost is the inverse Ackermann function, which is below 5 for any input that fits in a computer. Effectively constant, and the proof is famously not.

What it cannot do

Splitting. There is no efficient undo. If groups need to be broken apart, this is the wrong structure and the usual approach is to process the operations in reverse so that splits become merges.

It also does not tell you the path between two elements, only that one exists.

Where it is used

The Kruskal line if ru != rv is a find on each end. That is the entire cycle check, and it is why sorting the edges dominates the cost.