[算法笔记]带权并查集

带权并查集是普通并查集的进阶版本，功能更加强大。

普通并查集只能判断两个元素是否在一个集合中，带权并查集可以维护集合元素之间的关系，这个关系由每个元素的权值维护。

对权值的维护，我们需要在find()，unite()操作中分别进行修改。

例：399. 除法求值

class UnionFind {
public:
    unordered_map p;
    unordered_map d;

    UnionFind(vector>& equations, vector& values) {
        for (int i = 0; i < values.size(); i++) {
            string a = equations[i][0], b = equations[i][1];
            // 可能某个结点多次出现，防止对其初始化，导致覆盖
            if (!p.count(a)) {
                p[a] = a;
                d[a] = 1;
            }
            if (!p.count(b)) {
                p[b] = b;
                d[b] = 1 ;
            }
            unite(a, b, values[i]);
        }
    }
    string find(string x) {
        if (x != p[x]) {
            auto t = find(p[x]);
            d[x] *= d[p[x]];
            p[x] = t;
        }
        return p[x];
    }
    void unite(string a, string b, double v) {
        string ra = find(a), rb = find(b);
        if (ra != rb) {
            p[ra] = rb;
            d[ra] = v * d[b] / d[a];
        }
    }
};

初始化：a, b是两个需要合并的结点，v是它们的值，a，b满足一个关系式，即\(a / b = v\)。

find()：

? 我们同样进行路径压缩，路径压缩实际上就是将结点x，跳过x的父结点等等，直接与x的根结点相连。普通并查集我们可以直接相连，但是带权并查集我们需要维护结点权值。

? 如图，\(a->c\)的权值就等于\(a->b * b -> c\)，类似于带权有向图，我们要保证\(a->c\)的距离不变，换句话说，维护了\(a->b->c\)的路径权值和。

unite：

? 普通并查集中我们只要：

x = find(x), y = find(y);
p[x] = y;

? 带权并查集中：考虑$ x / y = v$。

? 结点x，y可能有多种情况，可能\(x == y, \ \ find(x) == x\ \ ||\ \ find(y) == y\)。

? 我们直接考虑最复杂的情况，即\(find(x) !!= x\ \ \&\& \ \ find(y) != y\)，这种情况是最复杂的，其他情况都是该情况的特殊情况！

? 观察图可得，蓝色线代表权值v（蓝色线不会相连，这里只是做出显示），为了维护 四边形法则（也就是X->Y无论从那条路径走，路径权值和应该相等），我们可以求得 \(V_x=V*V_2/V_1\) 。