vvrf / DSA.log

问题拆解

给定若干等式如 a / b = 2.0、b / c = 3.0，回答查询 a / c = ?；变量未出现过或推不出来时返回 -1。

孤立地看每条等式推不远，但注意除法的传递性：a / c = (a / b) × (b / c)。这个“相乘可传递”的结构正是图上的路径——把每个变量看成节点，等式 a / b = v 看成一条 a → b、权重为 v 的有向边，同时反向补一条权重 1 / v 的边（b / a 自然是倒数）。于是查询 x / y 就等价于：从 x 出发找一条到 y 的路径，沿途边权的乘积就是答案。

只要一种关系满足“可复合、可取逆”，就能建成带权图，把代数推导变成路径搜索——汇率换算、单位换算都是同一个模型。

建带权图，每个查询一次 DFS

用哈希表套哈希表存邻接关系：graph[a][b] = a / b。每个查询从起点 DFS，带一个 visited 集合防止绕圈，走到终点时返回累乘的结果。三种失败情形都返回 -1：变量根本没出现过、两点不连通、以及 x / x 但 x 未知（未知量不能凭空等于 1）。

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    Map<String, Map<String, Double>> graph = new HashMap<>();
    for (int i = 0; i < equations.size(); i++) {
        String a = equations.get(i).get(0), b = equations.get(i).get(1);
        graph.computeIfAbsent(a, k -> new HashMap<>()).put(b, values[i]);
        graph.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / values[i]); // 反向边取倒数
    }
    double[] ans = new double[queries.size()];
    for (int i = 0; i < queries.size(); i++) {
        String x = queries.get(i).get(0), y = queries.get(i).get(1);
        if (!graph.containsKey(x) || !graph.containsKey(y)) {
            ans[i] = -1.0; // 变量没出现过
        } else {
            ans[i] = dfs(graph, x, y, new HashSet<>());
        }
    }
    return ans;
}

private double dfs(Map<String, Map<String, Double>> graph, String cur, String target, Set<String> visited) {
    if (cur.equals(target)) {
        return 1.0;
    }
    visited.add(cur);
    for (Map.Entry<String, Double> e : graph.get(cur).entrySet()) {
        if (visited.contains(e.getKey())) {
            continue;
        }
        double sub = dfs(graph, e.getKey(), target, visited);
        if (sub != -1.0) {
            return e.getValue() * sub; // 边权乘上子路径的结果
        }
    }
    return -1.0;
}

def calcEquation(
    equations: List[List[str]], values: List[float], queries: List[List[str]]
) -> List[float]:
    graph = defaultdict(dict)
    for (a, b), v in zip(equations, values):
        graph[a][b] = v
        graph[b][a] = 1.0 / v  # 反向边取倒数

    def dfs(cur, target, visited):
        if cur == target:
            return 1.0
        visited.add(cur)
        for nxt, w in graph[cur].items():
            if nxt in visited:
                continue
            sub = dfs(nxt, target, visited)
            if sub != -1.0:
                return w * sub  # 边权乘上子路径的结果
        return -1.0

    return [
        dfs(x, y, set()) if x in graph and y in graph else -1.0  # 变量没出现过
        for x, y in queries
    ]

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    graph := map[string]map[string]float64{}
    addEdge := func(a, b string, v float64) {
        if graph[a] == nil {
            graph[a] = map[string]float64{}
        }
        graph[a][b] = v
    }
    for i, eq := range equations {
        addEdge(eq[0], eq[1], values[i])
        addEdge(eq[1], eq[0], 1.0/values[i]) // 反向边取倒数
    }
    var dfs func(cur, target string, visited map[string]bool) float64
    dfs = func(cur, target string, visited map[string]bool) float64 {
        if cur == target {
            return 1.0
        }
        visited[cur] = true
        for nxt, w := range graph[cur] {
            if visited[nxt] {
                continue
            }
            if sub := dfs(nxt, target, visited); sub != -1.0 {
                return w * sub // 边权乘上子路径的结果
            }
        }
        return -1.0
    }
    ans := make([]float64, len(queries))
    for i, q := range queries {
        if graph[q[0]] == nil || graph[q[1]] == nil {
            ans[i] = -1.0 // 变量没出现过
        } else {
            ans[i] = dfs(q[0], q[1], map[string]bool{})
        }
    }
    return ans
}

use std::collections::{HashMap, HashSet};

pub fn calc_equation(
    equations: Vec<Vec<String>>,
    values: Vec<f64>,
    queries: Vec<Vec<String>>,
) -> Vec<f64> {
    let mut graph: HashMap<&str, Vec<(&str, f64)>> = HashMap::new();
    for (eq, &v) in equations.iter().zip(values.iter()) {
        graph.entry(&eq[0]).or_default().push((&eq[1], v));
        graph.entry(&eq[1]).or_default().push((&eq[0], 1.0 / v)); // 反向边取倒数
    }

    fn dfs<'a>(
        graph: &HashMap<&'a str, Vec<(&'a str, f64)>>,
        cur: &'a str,
        target: &str,
        visited: &mut HashSet<&'a str>,
    ) -> f64 {
        if cur == target {
            return 1.0;
        }
        visited.insert(cur);
        for &(nxt, w) in graph[cur].iter() {
            if visited.contains(nxt) {
                continue;
            }
            let sub = dfs(graph, nxt, target, visited);
            if sub != -1.0 {
                return w * sub; // 边权乘上子路径的结果
            }
        }
        -1.0
    }

    queries
        .iter()
        .map(|q| {
            if !graph.contains_key(q[0].as_str()) || !graph.contains_key(q[1].as_str()) {
                -1.0 // 变量没出现过
            } else {
                dfs(&graph, &q[0], &q[1], &mut HashSet::new())
            }
        })
        .collect()
}

两个容易踩的坑。一是 x / x 类查询：如果 x 在图里，答案是 1；如果 x 从未出现过，答案是 -1——所以“变量是否存在”的检查必须放在 DFS 之前，不能靠 cur == target 一并处理。二是 visited 集合必须每个查询独立一份，且题目保证输入无矛盾，任意一条连通路径算出的值都相同，所以 DFS 找到第一条路径就可以直接返回。查询量很大时可以改用带权并查集把每个变量压到同一基准上，单次查询降到近 O(1)，但这题的数据规模用 DFS 足够。

复杂度

指标	复杂度	原因
时间	`O(q × (v + e))`	q 个查询各做一次 DFS，v、e 为变量数与等式数
空间	`O(v + e)`	邻接表，加上每次 DFS 的 visited 与递归栈

可以迁移的模式

关系可复合（相乘、相加）且可取逆时，把实体建成节点、关系建成带权双向边，推导即路径搜索；
图上找路径的 DFS 标配 visited 防环，权重沿路径累积（这里是乘法，最短路里是加法）；
区分“节点不存在”和“节点存在但不连通”两种失败，前者要在搜索前拦截。

把“汇率表里美元换日元怎么算”这种日常问题抽象成图，是这题最值得带走的东西。