Graph: Problem Solving7 sections · 191 units
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