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

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

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

Graph: groups merging

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