除法求值
Evaluate Division
题目详情
问题：除法求值
考察：数组、深度优先搜索、广度优先搜索
来源：DSA Prep / Citadel
链接：https://leetcode.com/problems/evaluate-division
英文原题
Problem: Evaluate Division
Patterns: Array, Depth-First Search, Breadth-First Search
Recency: 6mo
Link: https://leetcode.com/problems/evaluate-division
Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/
解析
思路：把等式 a / b = v 建成带权有向图，加入 a->b 权重 v 和 b->a 权重 1/v。每个查询用 DFS/BFS 从起点找终点，沿途乘权重。
复杂度：建图 O(E)，单次查询 O(V+E)，空间 O(V+E)。
英文解析
Approach: Build a weighted graph where `a / b = v` becomes edges `a -> b` with weight `v` and `b -> a` with weight `1/v`. Answer each query by DFS/BFS multiplying edge weights along the path.
Complexity: Build time ; each query is in the worst case.