Disjoint Set Union

Disjoint Set Union (DSU) helps manage groups.

It answers: - Are two items connected? - Can we merge two groups?

Real examples - friend networks - computer networks - clustering

Basic structure ```python class DSU: def __init__(self, n): self.parent = list(range(n))

def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x]

def union(self, a, b): pa, pb = self.find(a), self.find(b) if pa != pb: self.parent[pb] = pa ```

Usage ```python dsu = DSU(5) dsu.union(0, 1) dsu.union(1, 2) print(dsu.find(0) == dsu.find(2)) # True ```

Graph: groups merging ```mermaid flowchart LR A[0] --> B[1] B --> C[2] D[3] --> E[4] ```

Remember - find() locates group leader - union() merges groups - path compression makes it fast