带边权的并查集

字数统计: 2k字 | 阅读时长: 8分

2020-08-24

摘要: 带边权并查集的原理与代码模板

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章并查集中我们学习了并查集的原理和代码模板，本文介绍带边权并查集。

我们知道并查集的结构是一个森林，其中的每一棵树表示一个集合或者一个连通分量，树根元素为该集合的代表元，树中的各个节点分别代表各个元素。

有时我们需要在合并的过程中维护连通分量的某种属性，比如元素个数、最值等等，称为集合级的权。维护这种集合级的权，只需要在基础的并查集上增加很少代码即可实现，下面直接给出一些题目。

有时我们需要维护某种依赖于树的具体结构的信息，比如某节点到根节点得长度信息。这种信息取决于这棵树的具体结构，称为边级的权。

本文我们以力扣 399 为模板题，看一下带边权并查集到底是怎么应用的，代码如何实现。

$1 带边权并查集

带边权并查集，也就是带有边级信息的并查集，与并查集的区别就是并查集的树的边的意义不在只是相连，而又多了记录值(权) d[x]。这个权代表节点到其父节点这条有向边的某种指标，例如距离，d[x] := x -> father[x] 的距离。且这种指标要可以按某种规则传递，例如距离可以按加法传递，其它常见的规则还有乘法。

在查找和合并过程中都会对边级的权带来变化。

$2 含边权的并查集的查找和合并

下面以乘法传递为例。

查找

1	int find(int x)

如果当前节点不是根节点，先递归地找到当前节点在路径压缩后的父节点即根节点，记录下来。然后在回溯阶段，将当前节点连接到路径压缩后的父节点(根)之前，先用旧的父节点更新当前节点的权值，这里更新好的权值在继续回溯后还要被上一个节点使用。

1 2	// 种类权值信息是乘法传递的，所以用 = _weight[x] = _weight[_father[x]];

因为是从根开始回溯的，所有回溯完成后，所有 x -> 树根的路径上的节点 i ，它们记录的权值 _weight[i] 都改成了 x 到树根的距离。

int _find(int x)
{
    if(_father[x] == x)
        return x;
    int new_fa = _find(_father[x]);; // 路径压缩后的父节点
    _weight[x] *= _weight[_father[x]];
    _father[x] = new_fa;
    return _father[x];
}

合并

1	void merge(int x, int y, int w)

先求 x 和 y 的树根：

1 2	int rootx = _find(x); int rooty = _find(y);

x 到 rootx；y 到 rooty 之间路径上的点的权值在 _find() 里已经更新好了。之后要看 rootx 和 rooty 的树高，来决定是把 rootx 连接到 rooty 还是把 rooty 连接到 rootx。连接之后，要记录 rootx 或者 rooty 的信息。

比如将 rootx 连接到 rooty，那么需要更新 rootx 的权为 rootx 到 rooty 的距离。

1 2	_father[rootx] = rooty; _weight[rootx] = _weight[y] * w / _weight[x];

更新的时候利用到了 x -> y 的距离 w。x, rootx, y, rooty 构成一个四边形，从 x 走到对角 rooty 的两条路长度相等，可以推出 rootx -> rooty 的距离

$3 模板题

399. 除法求值

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回所有问题的答案。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

注意：未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。

提示：

1 <= equations.length <= 20
equations[i].length == 2
1 <= Ai.length, Bi.length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= Cj.length, Dj.length <= 5
Ai, Bi, Cj, Dj 由小写英文字母与数字组成

示例 1：
输入：equations = [[“a”,”b”],[“b”,”c”]], values = [2.0,3.0], queries = [[“a”,”c”],[“b”,”a”],[“a”,”e”],[“a”,”a”],[“x”,”x”]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
注意：x 是未定义的 => -1.0

示例 2：
输入：equations = [[“a”,”b”],[“b”,”c”],[“bc”,”cd”]], values = [1.5,2.5,5.0], queries = [[“a”,”c”],[“c”,”b”],[“bc”,”cd”],[“cd”,”bc”]]
输出：[3.75000,0.40000,5.00000,0.20000]

示例 3：
输入：equations = [[“a”,”b”]], values = [0.5], queries = [[“a”,”b”],[“b”,”a”],[“a”,”c”],[“x”,”y”]]
输出：[0.50000,2.00000,-1.00000,-1.00000]

算法：带边权并查集

算法：

1. 先遍历一遍已知等式，用哈希表记录已知等式中变量字符串对应的 id
2. 再遍历一遍已知等式，建立带权并查集。
3. 枚举每个询问，如果有变量不在并查集中(哈希表中查不到当前的变量字符串)；或者两个变量不在一个连通分量中(并查集的same函数返回false)，返回-1。
4. 否则，返回两个变量到根节点的权值，计算答案

代码 (C++，模板)

普通并查集的模板中，增加 weight[x], 维护 x -> father[x] 这条边的权值。

class WeightUnionFindSet
{
public:
    WeightUnionFindSet(int N)
    {
        _father = vector<int>(N, -1);
        _rank = vector<int>(N, 1);
        _weight = vector<double>(N, 1.0); // a / a = 1.0
        for(int i = 0; i < N; ++i)
            _father[i] = i;
    }

    bool same(int x, int y)
    {
        return _find(x) == _find(y);
    }

    double get_weight(int x)
    {
        _find(x);
        return _weight[x];
    }

    void merge(int x, int y, double w)
    {
        int rootx = _find(x);
        int rooty = _find(y);
        if(rootx == rooty) return;
        if(_rank[rootx] < _rank[rooty])
        {
            _father[rootx] = rooty;
            _weight[rootx] = _weight[y] * w / _weight[x];
        }
        else
        {
            _father[rooty] = rootx;
            _weight[rooty] = _weight[x] * (1 / w) / _weight[y];
        }
        if(_rank[rootx] == _rank[rooty])
            ++_rank[rootx];
    }

private:
    vector<int> _father;
    vector<int> _rank;
    vector<double> _weight;

    int _find(int x)
    {
        if(_father[x] == x)
            return x;
        int new_fa = _find(_father[x]);; // 路径压缩后的父节点
        _weight[x] *= _weight[_father[x]];
        _father[x] = new_fa;
        return _father[x];
    }
};

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        if(equations.empty()) return vector<double>((int)queries.size(), -1.0);
        int n = equations.size();
        unordered_map<string, int> item_id;
        int N = 0;
        for(const vector<string> &equation: equations)
        {
            for(const string &item: equation)
            {
                auto it = item_id.find(item);
                if(it == item_id.end())
                    item_id[item] = N++;
            }
        }
        WeightUnionFindSet weightunionfindset(N);
        for(int i = 0; i < n; ++i)
        {
            int x = item_id[equations[i][0]];
            int y = item_id[equations[i][1]];
            double w = values[i];
            if(!weightunionfindset.same(x, y))
                weightunionfindset.merge(x, y, w);
        }
        vector<double> result;
        for(const vector<string> &query: queries)
        {
            if(item_id.find(query[0]) == item_id.end() || item_id.find(query[1]) == item_id.end())
            {
                result.push_back(-1.0);
                continue;
            }
            int x = item_id[query[0]], y = item_id[query[1]];
            if(!weightunionfindset.same(x, y))
            {
                result.push_back(-1.0);
                continue;
            }
            double tmp = weightunionfindset.get_weight(x) / weightunionfindset.get_weight(y);
            result.push_back(tmp);
        }
        return result;
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法图算法