Union + Find算法的应用(不相交集)

Question

问题陈述:

方程以格式给出A / B = k,其中A和B是表示为字符串的变量,并且k是实数(浮点数).

给出一些查询,返回答案.如果答案不存在,则返回-1.0.

示例:给定 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 ]

输入是:

vector<pair<string, string>> equations
vector<double>& values
vector<pair<string, string>> queries 

在哪里equations.size() == values.size(),价值是积极的.

这代表方程式.

返回vector<double>.

根据上面的例子:等式= [ ["a", "b"], ["b", "c"] ]

values = [2.0, 3.0]

queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]

输入始终有效.您可以假设评估查询将导致不归零,并且没有矛盾.

解决方案 这可以使用Union + Find在不相交集上解决,这里可以看到一个解决方案:

解

但是,我不清楚第59行背后的直觉:

rst[i] = uf.rank.get(queries[i][0]) / uf.rank.get(queries[i][1]);

以及第99行:

rank.put(aFather, quotient * rank.get(b) / rank.get(a));

Answer 1

跟踪发生的事情并不难。事实上相当聪明！

让我们举一个更复杂的例子：

a / b = 2.0, b / c = 3.0, c / d = 4.0, d / e = 5.0

在第一步（由MakeSet触发UnionFind uf = new UnionFind(set)）期间，每个元素都被设置为其自己的父元素，并且所有等级都设置为 1.0：

parent(a) = a, rank(a) = 1.0
...
parent(e) = e, rank(e) = 1.0

在并集步骤中，节点的等级设置为给定的商，而父节点的等级保持不变（第 99 行）。因此，union(a, b, 2.0) parent(a) = b, rank(a) = 2.0对于任何节点 n: ，保持不变式，rank(n)/rank(parent(n)) = value其中值来自正在处理的方程（quotient参数）。最后我们得到：

parent(a) = b, rank(a) = 2.0
parent(b) = c, rank(b) = 3.0
parent(c) = d, rank(c) = 4.0
parent(d) = e, rank(d) = 5.0
parent(e) = e, rank(e) = 1.0

在压缩步骤中，如果正在搜索的节点的父节点不是集合的代表节点，则通过递归搜索父节点的父节点的父节点将其设置为...并设置当前节点的排名节点的当前等级乘以父级的等级（第 87 行）。所以最终我们得出：

parent(a) = e, rank(a) = 120.0
parent(b) = e, rank(b) = 60.0
parent(c) = e, rank(c) = 20.0
parent(d) = e, rank(d) = 5.0
parent(e) = e, rank(e) = 1.0

因此，确实有rank(a)=rank(b)*2.0，rank(b)=rank(c)*3.0等，正如输入方程中给出的那样。

请注意，集合的代表节点（即本例中的最终父节点e）最终的排名始终为 1.0。这就是为什么重复调用compressedFind和执行第 87 行不会进一步更改节点的等级（一旦计算完节点并设置了父节点）。

现在很容易看出第 59 行是如何工作的：如果查询是 a / b 则rank(a) /rank(b) = 120.0 / 60.0 = 2.0

这里使用的术语： https: //en.wikipedia.org/wiki/Disjoint-set_data_struct