Weighted Union-Find

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:
    function init(n):
        this.parent = array of [0, 1, ..., n-1]
        this.weight = array of n ones (1.0) // weight[i] = ratio to parent

    function find(x):
        if this.parent[x] != x:
            root = this.find(this.parent[x])
            this.weight[x] *= this.weight[this.parent[x]]
            this.parent[x] = root
        return this.parent[x]

During path compression, multiply weights along the path. After find, weight[x] gives the ratio from $x$ to root.