除法求值 图解题解

除法求值这道题在问什么

输入一批已知等式，比如 a/b=2、b/c=3，再给一批查询，要求推出每个查询的比值，例如 a/c 是多少。变量的具体数值从头到尾都不知道，能依赖的只有比值之间的关系。推不出来的情况一律返回 -1.0，包括两种：查询里出现了等式中从没出现过的变量（哪怕是 x/x 也不行），或者两个变量之间没有任何比值链条能连通。

为什么除法求值要建成带权图

关键观察是除法关系可以传递：a/b 乘以 b/c，分子分母里的 b 约掉，正好得到 a/c。也就是说，只要存在一串首尾相接的已知比值，把它们连乘就能推出新比值。「首尾相接的一串关系」在数据结构里的标准形态就是图上的一条路径——于是把每个变量看作节点，把 a/b=k 看作从 a 到 b、权值为 k 的有向边，「求 c/d」就变成了「在图上找一条 c 到 d 的路径，把沿途边权乘起来」。

一旦完成这步转化，题目就从陌生的代数推理，落回熟悉的图遍历模板，这正是本题被归为图论题的原因。

为什么每个等式必须建正反两条边

a/b=k 蕴含 b/a=1/k，这条反向信息不建进图里就丢了。只加正向边的话，图上从 b 走不到 a，b/a 这类逆着问的查询会被误判成推不出而返回 -1.0。所以建图时每个等式落两条边：a 到 b 权 k，b 到 a 权 1/k。用哈希表套哈希表做邻接表，节点是变量名字符串，取边和查邻居都是平均 O(1)。

DFS 连乘为什么是对的，seen 集合防什么

搜索函数 dfs(x, y, seen) 回答「从 x 到 y 的比值是多少」。它枚举 x 的每个邻居 nxt：x 到 nxt 的边权是 x/nxt 的值，子问题递归解出 nxt/y，两数相乘时中间项 nxt 约掉，正好是 x/y——每一步的正确性都还原成那条约分恒等式。起点与终点相同时返回 1.0，因为任何数除以自己是 1；任一变量不在图里则直接返回 -1.0，这个存在性检查必须放在最前面。

seen 集合记录本次查询已经走过的节点，防的是死循环：正反两条边天然构成来回的环，不挡住回头路，递归会在 a、b 之间无限弹跳直到爆栈。每次新查询都换一个空的 seen，互不干扰。

复杂度与查询很多时的优化

建图 O(E)；每个查询一次 DFS，最坏把 V 个点、E 条边都摸一遍，Q 个查询整体 O(Q·(V+E))，空间 O(V+E) 花在邻接表、递归栈和 seen 上。

如果查询量远大于图的规模，可以把「现查」换成「预处理」：用 Floyd 一次算出所有点对的比值，预处理 O(V³) 之后每个查询 O(1)；或者用带权并查集，把比值压缩到每个节点相对根的倍率上，同一集合内任意两点的比值近 O(1) 可得。查询少时，朴素 DFS 就是性价比最高的写法。

Python

def calcEquation(equations, values, queries):
    g = {}
    for (a, b), k in zip(equations, values):
        g.setdefault(a, {})[b] = k
        g.setdefault(b, {})[a] = 1.0 / k
    def dfs(x, y, seen):
        if x not in g or y not in g: return -1.0
        if x == y: return 1.0
        seen.add(x)
        for nxt, w in g[x].items():
            if nxt in seen: continue
            r = dfs(nxt, y, seen)
            if r != -1.0: return w * r
        return -1.0
    return [dfs(c, d, set()) for c, d in queries]

C++

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
unordered_map<string, unordered_map<string,double>> g;
double dfs(const string& x, const string& y, unordered_set<string>& seen){
    if(!g.count(x) || !g.count(y)) return -1.0;
    if(x == y) return 1.0;
    seen.insert(x);
    for(auto& [nxt, w] : g[x]){
        if(seen.count(nxt)) continue;
        double r = dfs(nxt, y, seen);
        if(r != -1.0) return w * r;
    }
    return -1.0;
}
vector<double> calcEquation(vector<vector<string>>& eq, vector<double>& val, vector<vector<string>>& q){
    for(int i = 0; i < (int)eq.size(); i++){
        g[eq[i][0]][eq[i][1]] = val[i];
        g[eq[i][1]][eq[i][0]] = 1.0 / val[i];
    }
    vector<double> ans;
    for(auto& c : q){ unordered_set<string> s; ans.push_back(dfs(c[0], c[1], s)); }
    return ans;
}

Java

import java.util.*;
class Solution {
    Map<String, Map<String, Double>> g = new HashMap<>();
    public double[] calcEquation(List<List<String>> equations,
                                 double[] values, List<List<String>> queries) {
        for (int i = 0; i < values.length; i++) {
            String a = equations.get(i).get(0), b = equations.get(i).get(1);
            g.computeIfAbsent(a, z -> new HashMap<>()).put(b, values[i]);
            g.computeIfAbsent(b, z -> new HashMap<>()).put(a, 1.0 / values[i]);
        }
        double[] ans = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String c = queries.get(i).get(0), d = queries.get(i).get(1);
            ans[i] = dfs(c, d, new HashSet<>());
        }
        return ans;
    }
    double dfs(String x, String y, Set<String> seen) {
        if (!g.containsKey(x) || !g.containsKey(y)) return -1.0;
        if (x.equals(y)) return 1.0;
        seen.add(x);
        for (Map.Entry<String, Double> e : g.get(x).entrySet()) {
            if (seen.contains(e.getKey())) continue;
            double r = dfs(e.getKey(), y, seen);
            if (r != -1.0) return e.getValue() * r;
        }
        return -1.0;
    }
}