Union-Find (Disjoint Set Union)

Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
Union: Join two subsets into a single subset.

A common application of Union-Find is to detect cycles in an undirected graph. For each edge (u, v) in the graph, if find(u) is the same as find(v), then adding this edge would form a cycle. Otherwise, you can union(u, v).

To make the operations efficient, two optimizations are commonly used:

Path Compression: During a find operation, make every node on the find path point directly to the root. This flattens the tree structure.
Union by Rank/Size: When merging two sets, attach the smaller tree to the root of the larger tree. This helps to keep the trees from becoming too deep.

With these optimizations, the time complexity of the operations becomes nearly constant on average.

Union-Find Data Structure

Step 1 of 0

Current Operation

Initialize

Action

Ready to start

Connected Components:

Currently Active

In Find Path

Root Node

Regular Node

Active Path

Union-Find Operations: Find(x) - finds root with path compression. Union(x,y) - merges sets using union by rank. Near O(1) amortized time per operation.

Union-Find (Disjoint Set Union)

The Union-Find data structure, also known as Disjoint Set Union (DSU), is used to keep track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It's particularly useful for detecting cycles in an undirected graph and in Kruskal's algorithm for finding a Minimum Spanning Tree.

Key Operations

Find: Determine which subset an element belongs to. This can be used for determining if two elements are in the same subset.
Union: Join two subsets into a single subset.

Union-Find


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n

    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])  # Path compression
        return self.parent[i]

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            # Union by rank
            if self.rank[root_i] > self.rank[root_j]:
                self.parent[root_j] = root_i
            elif self.rank[root_i] < self.rank[root_j]:
                self.parent[root_i] = root_j
            else:
                self.parent[root_j] = root_i
                self.rank[root_i] += 1
            return True
        return False