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

$ curl repovive.com/roadmaps/graph-problem-solving/connectivity-dsu-and-dfs/union-find-with-path-compression-and-rank

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

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

$ curl repovive.com/roadmaps/graph-problem-solving/connectivity-dsu-and-dfs/union-find-with-path-compression-and-rank

Repovive

Union-Find with Path Compression and Rank - Connectivity (DSU and DFS) | Graph: Problem Solving | Repovive

Repovive.

Graph: Problem Solving7 sections · 191 units16h total

Open in Course

Union-Find with Path Compression and Rank

The data structure

Here is the optimized Union-Find template. You can take a look at now, in the next units, I will explain what each part is doing.


function find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

function union(x, y):
    px, py = find(x), find(y)
    if px == py: return false
    if rank[px] < rank[py]: swap(px, py)
    parent[py] = px
    if rank[px] == rank[py]: rank[px]++
    return true