java - Union+Find算法的应用(Disjoint Set)

Question

问题陈述:

方程式以 A / B = k 格式给出, 其中A和 B是表示为字符串的变量，k是实数( float )。

给出一些查询，返回答案。如果答案不存在，返回-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"] ]

值 = [2.0, 3.0]

查询 = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]

输入始终有效。您可能会假设评估查询不会导致除以零并且不存在矛盾。

解决方案这可以在不相交的集合上使用 Union+Find 来解决，这里有一个解决方案:

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));

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，其中 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

在压缩步骤中，如果被搜索节点的父节点不是集合的代表节点，则通过递归搜索设置为parent of parent of parent... 并将当前节点的等级设置为当前等级乘以父等级(第 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