python-leetcode-除法求值

399. 除法求值 - 力扣（LeetCode）

from collections import defaultdict
from typing import List

class 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] = value
            graph[B][A] = 1 / value  # 反向边

        # DFS 计算路径上的乘积
        def dfs(x, y, visited):
            if x not in graph or y not in graph:
                return -1.0
            if x == y:
                return 1.0
            
            visited.add(x)
            for neighbor in graph[x]:
                if neighbor in visited:
                    continue
                weight = graph[x][neighbor]
                res = dfs(neighbor, y, visited)
                if res != -1.0:  # 找到有效路径
                    return weight * res
            return -1.0

        # 处理查询
        results = []
        for C, D in queries:
            results.append(dfs(C, D, set()))
        
        return results