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>。

根据上面的例子： equations = [ ["a", "b"], ["b", "c"] ]

values = [2.0, 3.0]

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

输入始终有效。您可以假设计算查询将不会出现除以零的情况，并且不存在矛盾。

解决方案 这可以使用在不相交集合上的并+查找进行求解，可以看到以下解决方案:

Solution

然而，我不清楚第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));

- user1008636

---

这里的主要想法是存储（第99行）xFather/a和xFather/b，其中 xFather 是 a 和 b 的共同父亲。当您需要 a/b 比率时，只需执行 (xFather/b)/(xFather/a)(第59行) 即可。 - miradham

如果没有版权问题，你应该在这里粘贴代码，而不是指向 GitHub。这样，如果那里的代码发生更改或被删除，这个问题仍然能够保持连贯性。 - Michael Veksler

Answer 1

我很容易理解发生了什么。实际上相当聪明！

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

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

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

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

在 Union 步骤中，节点的等级设置为给定的商数，而父节点的等级保持不变（第99行）。 因此，在执行 union(a, b, 2.0) 后，parent(a) = b, rank(a) = 2.0，并且对于任何节点n都满足不变式：rank(n)/rank(parent(n)) = value，其中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_structure

- memo