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

$ curl repovive.com/roadmaps/data-structures/union-find/evaluate-division-weighted-uf

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

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

$ curl repovive.com/roadmaps/data-structures/union-find/evaluate-division-weighted-uf

Repovive

Evaluate Division: Weighted UF - Union-Find | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units

Open in Course

Evaluate Division: Weighted UF

Ratios as weights

Map variable names to indices. For equation $a/b = v$ :

Union $a$ and $b$ with weight $v$

To query $a/c$ :

Find roots of both
If different roots, return $-1$
If same root, return $\text{weight}[a] / \text{weight}[c]$

def find(x):
    if parent[x] != x:
        originalParent = parent[x]
        parent[x] = find(parent[x])
        weight[x] *= weight[originalParent]
    return parent[x]

def union(a, b, val):
    rootA, rootB = find(a), find(b)
    if rootA == rootB:
        return
    # rootA/rootB = weight[b] * val / weight[a]
    parent[rootA] = rootB
    weight[rootA] = weight[b] * val / weight[a]

The weight calculation during union ensures consistency.

HannahHi! I'm Hannah. Let me know if you need help understanding anything!