LC399 · Evaluate Division · 图 / DFS

除法求值：比值是带权边，查询是路径乘积

a/b=2 给 a→b 权 2、b→a 权 0.5。查 a/c 就是从 a 走到 c，把边权乘起来。走不到返回 −1。

建带权有向图：等式 a/b=val 加边 a→b 权 val、b→a 权 1/val。每次查询从起点 DFS，累乘边权；走到终点就返回乘积，不可达返回 −1。并查集带权是同一件事的压缩写法。时间 O(Q·V)，空间 O(V+E)。

时间 O(Q·V)空间 O(V+E)结论先行 · 全文约 6 节

导读

这是 LeetCode 399. Evaluate Division。给你一组等式 equations[i] = [ai, bi] 和 values[i]，表示 ai/bi = values[i]。再给若干查询 [cj, dj]，求 cj/dj。变量是字符串。除数不为 0。算不出来的查询返回 −1.0。

主例只有两条：a/b=2，b/c=3。查询 a/c。中间隔着 b：a/c = (a/b)·(b/c) = 2×3 = 6。演示沿 a→b→c 把乘积从 1 累到 2 再累到 6。

第一直觉是把每对等式存进哈希表，查询时直接读。主例的 a/c 根本没出现过，表里没有。缺的是传递：已知 a 对 b、b 对 c，要推出 a 对 c。下面把比值画成边，用路径乘积补上这段缺口。

一

边权相乘就是除法链式法则

一条等式只钉死两个变量的比值。变量是点；a/b=val 是 a 指向 b 的有向边，权就是 val。反过来 b/a 必须是 1/val，否则图上走回头会和除法矛盾。没有双向边，主例查 c/a 就走不通，其实答案该是 1/6。

缺的信息是「不直接相邻的两个变量怎么比」。暴力枚举中间变量写连等式，变量一多就组合爆炸，还容易漏。图把中间变量变成路径上的点：a/c = (a/b)·(b/c)，边权相乘正好是除法的链式法则。同一连通分量里任意两点的比值唯一，走哪条路乘积都一样；不在同一分量，或者变量根本没在等式里出现过，返回 −1。

从缺口反推两步。建图：扫一遍等式，给每个出现过的变量建邻接表，写入 val 和 1/val。查询：从 cj 出发 DFS 或 BFS，带着当前乘积 acc，走到 dj 就返回 acc；邻居用 seen 挡住，避免在无向意义上的环里转。起点终点是同一个已出现变量，乘积是 1。

用手走主例查询 a/c。起点 a，acc=1，路径 [a]。邻居只有 b，权 2，走到 b，acc=2，路径 [a,b]。b 的邻居有 a 和 c，a 已见过，走 c，权 3，acc=2×3=6，路径 [a,b,c]。from==to，返回 6。演示四帧就是这三次状态加一句结论。

并查集带权做的是同一件事：每个点记「自己除以根」的权，查询时若根相同，比值就是两个权相除。路径压缩要同步改权。图 DFS 更好讲清乘积从哪来；并查集在多次查询时更快。不要把「没出现过的变量」当成 1；也不要只建单向边。

乘积与路径无关比值在连通分量里是唯一的。a/c 走 a→b→c 得 6，若还有别的中间变量，乘积必须仍是 6，否则等式自相矛盾。所以找到第一条到达路径就可以返回。

a/b=2, b/c=3；查询 a/c

a/c = 1

起点 a，累计 1

二

Go：DFS 边权累乘

solution.goGo

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    adj := map[string]map[string]float64{}
    for i, eq := range equations {
        a, b := eq[0], eq[1]
        if adj[a] == nil { adj[a] = map[string]float64{} }
        if adj[b] == nil { adj[b] = map[string]float64{} }
        adj[a][b] = values[i]
        adj[b][a] = 1 / values[i]
    }
    var dfs func(string, string, float64, map[string]bool) float64
    dfs = func(from, to string, acc float64, seen map[string]bool) float64 {
        if from == to { return acc }
        seen[from] = true
        for nb, w := range adj[from] {
            if seen[nb] { continue }
            if r := dfs(nb, to, acc*w, seen); r >= 0 { return r }
        }
        return -1
    }
    res := []float64{}
    for _, q := range queries {
        res = append(res, dfs(q[0], q[1], 1, map[string]bool{}))
    }
    return res
}

1每条等式写两向边：正向 val，反向 1/val。漏掉反向，主例的 c/a 会变成 −1。

2DFS 带着 acc 往前走，走到 to 就返回 acc。邻居用 seen 去环。走不通返回 −1。

3每次查询换一份 seen，从乘积 1 重新出发。图是共享的，不必每查一次重建。

总结

比值画成带权边，查询沿路径累乘。主例 a→b→c 得到 6。

只存直接等式不够。a/c 要靠中间变量把边接起来。
必须建反向边。同一分量里乘积唯一，找到一条路径即可。
并查集带权是压缩版：比的是各自到根的权。

同族题目

LC207课程表LC684冗余连接LC547省份数量