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

$ curl repovive.com/roadmaps/graph-theory/disjoint-set-union-dsu/implementation-union-by-size

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

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

$ curl repovive.com/roadmaps/graph-theory/disjoint-set-union-dsu/implementation-union-by-size

Repovive

Implementation - Union by Size - Disjoint Set Union (DSU) | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Implementation - Union by Size

Coding the Merger

Here is the implementation:

function unite(i, j):
    rootA = find(i)
    rootB = find(j)
    if rootA != rootB:
        if size[rootA] < size[rootB]:
            swap(rootA, rootB)
        parent[rootB] = rootA
        size[rootA] = size[rootA] + size[rootB]

This runs in $O(\alpha(n))$ amortized time and uses $O(n)$ space.