Sometimes you need to track more than connectivity. Weighted Union-Find stores the relationship between each node and its parent.
Example: currency exchange. If 1 USD = 0.85 EUR, store this ratio. To find the exchange rate between any two currencies, multiply ratios along the path.
class WeightedUnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.weight = [1.0] * n # weight[i] = ratio to parent
def find(self, x):
if self.parent[x] != x:
root = self.find(self.parent[x])
self.weight[x] *= self.weight[self.parent[x]]
self.parent[x] = root
return self.parent[x]
During path compression, multiply weights along the path. After find, weight[x] gives the ratio from to root.