除法求值

怎样从“equations=[["a","b"],["b","c"]],values=[2,3],queries a/c。”推导出 图 DFS · 除法求值，并证明每次状态变化都不会漏掉答案？

中心结论：建加权有向图,a->b 权 2 则 b->a 权 1/2;DFS/BFS 求路径积。

给出方程式 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 > equations, vector & values, vector > queries(方程式，方程式结果，问题方程式)， 其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回vector 类型。

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

在本站主例中，equations=[["a","b"],["b","c"]],values=[2,3],queries a/c。

算法最终需要得到或观察：a/c=2/3。

重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“图搜索前线”，明确答案需要观察什么。
2. 2状态只维护 graph、visited、累积积。
3. 3转移每一步按照 建加权有向图,a->b 权 2 则 b->a 权 1/2;DFS/BFS 求路径积。
4. 4收尾读取 a/c=2/3。，并复核边界与复杂度。

先把题目对象翻译成节点和边，再选择 BFS 或 DFS。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：graph、visited、累积积。

给出一些字母变量的倍数关系，问给出任意两个字母的倍数是多少。 这一题可以用 DFS 或者并查集来解题。先来看看 DFS 的做法。先建图。每个字母或者字母组合可以看做成一个节点，给出的 `equations` 关系可以看成两个节点之间的有向边。每条有向边都有权值。那么问题可以转换成是否存在一条从起点节点到终点节点的路径，如果存在，输出这条路径上所有有向边权值的累乘结果。如果不存在这条路径，就返回 -1 。如果给的起点和终点不在给出的节点集里面，也输出 -1 。 再来看看并查集的做法。先将每两个有倍数关系的节点做并查集 `union()` 操作。例如 A/B = 2，那么把 B 作为 `parent` 节点，`parents[A] = {B，2}`，`parents[B] = {B，1}`，B 指向自己是 1 。还有一个关系是 `B/C=3`，由于 B 已经在并查集中了，所以这个时候需要把这个关系反过来，处理成 `C/B = 1/3` ，即 `parents[C] = {B，1/3}`。这样把所有有关系的字母都 `union()` 起来。如何求任意两个字母的倍数关系呢？例如 `A/C = ?` 在并查集中查找，可以找到 `parents[C] == parents[A] == B`，那么就用 `parents[A]/parents[C] = 2/(1/3) = 6`。为什么可以这样做呢？因为 `A/B = 2`，`C/B = 1/3`，那么 `A/C = (A/B)/(C/B)` 即 `parents[A]/parents[C] = 2/(1/3) = 6`。

建加权有向图,a->b 权 2 则 b->a 权 1/2;DFS/BFS 求路径积。

执行过程中持续维护：graph、visited、累积积。

正确性依赖以下不变量：路径积=边权连乘。

面试时可以压缩为：建图+DFS 求连通积 O(E+Q·(V+E))。

落到当前题，执行机制可以压缩为：建加权有向图,a->b 权 2 则 b->a 权 1/2;DFS/BFS 求路径积。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入equations=[["a","b"],["b","c"]],values=[2,3],queries a/c。 因为：建加权有向图,a->b 权 2 则 b->a 权 1/2;DFS/BFS 求路径积。
2. 2哈希 map: oldId → cloneId遇结点先查 map。 因为：避免重复克隆与死循环。
3. 3克隆结点 1 → 11复制结点值。 因为：再递归克隆邻居并连边。
4. 4克隆结点 2 → 12复制结点值。 因为：再递归克隆邻居并连边。
5. 5克隆结点 3 → 13复制结点值。 因为：再递归克隆邻居并连边。
6. 6深拷贝图完成map 中所有结点已复制。 因为：O(V+E) DFS + map。
7. 7哈希 map: oldId → cloneId遇结点先查 map。 因为：避免重复克隆与死循环。
8. 8收尾与复杂度a/c=2/3。 因为：时间 O(n) · 空间 O(1)。建加权有向图,a->b 权 2 则 b->a 权 1/2;DFS/BFS 求路径积。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

type stringUnionFind struct {
	parents map[string]string
	vals    map[string]float64
}

func (suf stringUnionFind) add(x string) {
	if _, ok := suf.parents[x]; ok {
		return
	}
	suf.parents[x] = x
	suf.vals[x] = 1.0
}

func (suf stringUnionFind) find(x string) string {
	p := suf.parents[x]
	if x != p {
		pp := suf.find(p)
		suf.vals[x] *= suf.vals[p]
		suf.parents[x] = pp
	}
	return suf.parents[x]
}

func (suf stringUnionFind) union(x, y string, v float64) {
	suf.add(x)
	suf.add(y)
	px, py := suf.find(x), suf.find(y)
	suf.parents[px] = py
	// x / px = vals[x]
	// x / y = v
	// 由上面 2 个式子就可以得出 px = v * vals[y] / vals[x]
	suf.vals[px] = v * suf.vals[y] / suf.vals[x]
}

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	res, suf := make([]float64, len(queries)), stringUnionFind{parents: map[string]string{}, vals: map[string]float64{}}
	for i := 0; i < len(values); i++ {
		suf.union(equations[i][0], equations[i][1], values[i])
	}
	for i := 0; i < len(queries); i++ {
		x, y := queries[i][0], queries[i][1]
		if _, ok := suf.parents[x]; ok {
			if _, ok := suf.parents[y]; ok {
				if suf.find(x) == suf.find(y) {
					res[i] = suf.vals[x] / suf.vals[y]
				} else {
					res[i] = -1
				}
			} else {
				res[i] = -1
			}
		} else {
			res[i] = -1
		}
	}
	return res
}

func main() {
    // 1. 主例
    //    输入：mode="clone-graph", numCourses=3
    //    期望：a/c=2/3。
    //
    // 2. 失败 / 未命中
    //    检查：除零/query 不存在返回 -1。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC200 岛屿；LC133 克隆
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意equations=[["a","b"],["b","c"]],values=[2,3],queries a/c。
2. 2重复重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。
3. 3优化建加权有向图,a->b 权 2 则 b->a 权 1/2;DFS/BFS 求路径积。
4. 4证明路径积=边权连乘。
5. 5复杂度时间 O(n)，空间 O(1)