#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/union-find/basic-union

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/union-find/basic-union

Repovive

Basic Union - Union-Find | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Basic Union

Merging two components

To merge components containing $x$ and $y$ , make one root point to the other:

def union(self, x, y):
    rootX = self.find(x)
    rootY = self.find(y)
    if rootX != rootY:
        self.parent[rootX] = rootY

After this, find(x) and find(y) return the same root.

Problem: without care, trees can become tall. if you union nodes $1, 2, 3, ..., n$ in order, you get a chain of length $n$ . Then find takes $O(n)$ time.

You need two optimizations:

$1.$ Path compression: flatten trees during find

$2.$ Union by rank/size: keep trees balanced during union

Together, these achieve nearly constant time per operation.