【并查集-2】399.除法求值

题目描述给你一个变量对数组equations和一个实数值数组values作为已知条件其中equations[i] [Ai, Bi]和values[i]共同表示等式Ai / Bi values[i]。每个Ai或Bi是一个表示单个变量的字符串。另有一些以数组queries表示的问题其中queries[j] [Cj, Dj]表示第j个问题请你根据已知条件找出Cj / Dj ?的结果作为答案。返回所有问题的答案。如果存在某个无法确定的答案则用-1.0替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串也需要用-1.0替代这个答案。注意输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况且不存在任何矛盾的结果。注意未在等式列表中出现的变量是未定义的因此无法确定它们的答案。示例 1输入equations [[a,b],[b,c]], values [2.0,3.0], queries [[a,c],[b,a],[a,e],[a,a],[x,x]]输出[6.00000,0.50000,-1.00000,1.00000,-1.00000]解释条件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 ] 注意x 是未定义的 -1.0示例 2输入equations [[a,b],[b,c],[bc,cd]], values [1.5,2.5,5.0], queries [[a,c],[c,b],[bc,cd],[cd,bc]]输出[3.75000,0.40000,5.00000,0.20000]示例 3输入equations [[a,b]], values [0.5], queries [[a,b],[b,a],[a,c],[x,y]]输出[0.50000,2.00000,-1.00000,-1.00000]解题思路方法一图 DFS/BFS核心思路建图对于A / B k从 A 到 B 有一条权重为k的边从 B 到 A 有一条权重为1/k的边这样A / C就转化为从 A 到 C 的路径上所有边的权重乘积。具体过程示例equations [[a,b],[b,c]], values [2.0, 3.0]a --2.0-- b --3.0-- c a --0.5-- b --1/3-- c a / c a-b-c 2.0 * 3.0 6.0查询逻辑如果from或to不在图中 → 返回-1.0如果from to→ 返回1.0否则从from出发 DFS/BFS 搜索到to沿途累乘权重代码实现DFSclass Solution { public: vectordouble calcEquation(vectorvectorstring equations, vectordouble values, vectorvectorstring queries) { // 建图邻接表存储 (邻居, 权重) unordered_mapstring, vectorpairstring, double graph; for (int i 0; i equations.size(); i) { string a equations[i][0], b equations[i][1]; double v values[i]; graph[a].push_back({b, v}); graph[b].push_back({a, 1.0 / v}); } vectordouble result; for (auto query : queries) { string from query[0], to query[1]; // 变量不存在 if (graph.find(from) graph.end() || graph.find(to) graph.end()) { result.push_back(-1.0); continue; } // 相同变量 if (from to) { result.push_back(1.0); continue; } // DFS 搜索 unordered_setstring visited; result.push_back(dfs(graph, from, to, 1.0, visited)); } return result; } private: double dfs(unordered_mapstring, vectorpairstring, double graph, string curr, string target, double value, unordered_setstring visited) { if (curr target) return value; if (visited.count(curr)) return -1.0; visited.insert(curr); for (auto [next, weight] : graph[curr]) { double res dfs(graph, next, target, value * weight, visited); if (res ! -1.0) return res; } return -1.0; } };复杂度分析设E是方程式数量Q是查询数量V是变量数量。维度复杂度说明时间复杂度O(Q × (V E))每个查询最坏遍历整个图空间复杂度O(V E)存储图和 visited方法二并查集带权并查集的核心权重定义weight[x] x / parent[x]如果x是根节点weight[x] 1.0查找时路径压缩需要更新权重合并逻辑已知a / b v要把a和b合并到同一集合找到a的根rootAb的根rootB如果rootA ! rootB把rootA接到rootB上需要计算rootA / rootB的值推导a / b v a weight[a] * rootA b weight[b] * rootB 所以: (weight[a] * rootA) / (weight[b] * rootB) v 即: rootA / rootB v * weight[b] / weight[a]所以weight[rootA] v * weight[b] / weight[a]。查询逻辑已知from和to如果它们不在同一集合 → 返回-1.0如果在同一集合from / to weight[from] / weight[to]代码实现class Solution { private: unordered_mapstring, string parent; // 父节点 unordered_mapstring, double weight; // weight[x] x / parent[x] // 查找根节点路径压缩 更新权重 string find(string x) { if (parent[x] ! x) { string root find(parent[x]); weight[x] * weight[parent[x]]; // 更新 x / root parent[x] root; } return parent[x]; } // 合并a / b v void unite(string a, string b, double v) { string rootA find(a); string rootB find(b); if (rootA rootB) return; // rootA / rootB v * weight[b] / weight[a] parent[rootA] rootB; weight[rootA] v * weight[b] / weight[a]; } public: vectordouble calcEquation(vectorvectorstring equations, vectordouble values, vectorvectorstring queries) { // 初始化每个变量是独立集合权重为 1 for (int i 0; i equations.size(); i) { string a equations[i][0], b equations[i][1]; if (parent.find(a) parent.end()) { parent[a] a; weight[a] 1.0; } if (parent.find(b) parent.end()) { parent[b] b; weight[b] 1.0; } unite(a, b, values[i]); } vectordouble result; for (auto query : queries) { string from query[0], to query[1]; // 变量不存在 if (parent.find(from) parent.end() || parent.find(to) parent.end()) { result.push_back(-1.0); continue; } string rootFrom find(from); string rootTo find(to); // 不在同一集合 if (rootFrom ! rootTo) { result.push_back(-1.0); continue; } // 在同一集合from / to weight[from] / weight[to] result.push_back(weight[from] / weight[to]); } return result; } };具体过程示例equations [[a,b],[b,c]], values [2.0, 3.0]初始化parent: {a:a, b:b, c:c} weight: {a:1.0, b:1.0, c:1.0}合并 a/b 2.0rootA a, rootB b parent[a] b weight[a] 2.0 * weight[b] / weight[a] 2.0 * 1.0 / 1.0 2.0 parent: {a:b, b:b, c:c} weight: {a:2.0, b:1.0, c:1.0}合并 b/c 3.0:rootB b, rootC c parent[b] c weight[b] 3.0 * weight[c] / weight[b] 3.0 * 1.0 / 1.0 3.0 parent: {a:b, b:c, c:c} weight: {a:2.0, b:3.0, c:1.0}查询 a/c:find(a): a-b-c路径压缩 weight[a] 2.0 * 3.0 6.0a/c parent[a] c find(c): c 是根weight[c] 1.0 a/c weight[a] / weight[c] 6.0 / 1.0 6.0 ✅复杂度分析:维度复杂度说明时间复杂度O((E Q) × α)α 是阿克曼函数反函数接近 O(1)空间复杂度O(V)parent 和 weight 哈希表E 是方程式数量Q 是查询数量V 是变量数量。关键细节:1. 路径压缩时为什么要更新权重string root find(parent[x]); weight[x] * weight[parent[x]]; parent[x] root;因为weight[x]原来表示x / parent[x]路径压缩后要变成x / root所以需要乘上parent[x] / root即weight[parent[x]]。2. 合并时 weight[rootA] 怎么算a / b v a weight[a] * rootA b weight[b] * rootB (weight[a] * rootA) / (weight[b] * rootB) v rootA / rootB v * weight[b] / weight[a]所以weight[rootA] v * weight[b] / weight[a]。3. 查询时为什么是weight[from] / weight[to]因为from / to (weight[from] * root) / (weight[to] * root) weight[from] / weight[to]根节点被约掉了。并查集 vs DFS/BFS:对比维度带权并查集DFS/BFS时间复杂度O((EQ) × α)O(Q × (VE))空间复杂度O(V)O(VE)查询速度接近 O(1)O(VE)代码复杂度较高中等推荐度⭐⭐⭐⭐⭐⭐⭐⭐⭐并查集适合查询多的场景DFS/BFS 代码更直观。