Q85: Connected Components & Disjoint Set Union (DSU). - DSA Patterns (Multi-Lang)

In Simple Words: DSU with Path Compression and Union by Rank:

find(x): recursively sets parent[x] = find(parent[x]).
union(x, y): attaches smaller tree under larger root, decrements component count if sets were disjoint.
Time: $O(\alpha(N)) \approx O(1)$ per operation | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n
        self.count = 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, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.count -= 1
        return True