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

$ 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 units49h total

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
 # weight[a] * val = weight[b] after union
 # So rootA's weight relative to rootB is weight[b] / (weight[a] * val)
 parent[rootA] = rootB
 weight[rootA] = weight[b] / (weight[a] * val)

The weight calculation during union ensures consistency.