399. 除法求值 - 力扣（LeetCode）
from collections import defaultdict
from typing import Listclass Solution:def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:# 构建加权图graph = defaultdict(dict)for (A, B), value in zip(equations, values):graph[A][B] = valuegraph[B][A] = 1 / value # 反向边# DFS 计算路径上的乘积def dfs(x, y, visited):if x not in graph or y not in graph:return -1.0if x == y:return 1.0visited.add(x)for neighbor in graph[x]:if neighbor in visited:continueweight = graph[x][neighbor]res = dfs(neighbor, y, visited)if res != -1.0: # 找到有效路径return weight * resreturn -1.0# 处理查询results = []for C, D in queries:results.append(dfs(C, D, set()))return results