class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 1. 构建邻接表（图）
        // graph 的 Key 是节点名称（变量），Value 是一个 Map，存储它连接到的邻居节点以及对应的边权重（除法结果）
        Map<String, Map<String, Double>> graph = new HashMap<>();
        
        // i：遍历整个 equations 集合，为每个等式构建双向边
        for (int i = 0; i < equations.size(); i++) {
            // left：当前等式被除数变量
            String left = equations.get(i).get(0);
            // right：当前等式除数变量
            String right = equations.get(i).get(1);
            // num：当前等式的结果（即 left / right 的值）
            double num = values[i];
            
            // 建立 left -> right 的边，权重为 num
            graph.computeIfAbsent(left, m -> new HashMap()).put(right, num);
            // 建立 right -> left 的边，权重为 1 / num（因为 right / left 是倒数关系）
            graph.computeIfAbsent(right, m -> new HashMap()).put(left, 1.0 / num);
        }
        
        // result：用于存储最终每个查询的结果数组
        double[] result = new double[queries.size()];
        
        // 2. 处理查询
        for (int i = 0; i < queries.size(); i++) {
            // left：当前查询的起点变量
            String left = queries.get(i).get(0);
            // right：当前查询的终点变量
            String right = queries.get(i).get(1);

            // 如果图中不存在 left 或 right 变量，该查询无法计算，直接置为 -1.0
            if (!graph.containsKey(left) || !graph.containsKey(right)) {
                result[i] = -1.0;
                continue;
            }
            
            // 如果起点和终点相同，结果必定为 1.0
            if (left.equals(right)) {
                result[i] = 1.0;
                continue;
            }
            
            // 调用 BFS 方法在图中寻找路径并计算乘积结果
            result[i] = bfs(graph, left, right);
        }
        return result;
    } 
    
    // bfs：广度优先搜索辅助函数，用于计算从 start 到 end 的路径乘积
    private double bfs(Map<String, Map<String, Double>> graph, String start, String end) {
        // queue：用于 BFS 遍历的队列，存放即将探索的节点
        Queue<String> queue = new LinkedList<>();
        // map：记录已经访问过的节点，以及从起点 start 到该节点的累积乘积结果
        Map<String, Double> map = new HashMap<>();

        queue.offer(start);
        map.put(start, 1.0);

        while (!queue.isEmpty()) {
            // 从队列中弹出一个当前正在访问的节点
            String current = queue.poll();
            // currentVal：从起点 start 到当前节点 current 的累积乘积值
            double currentVal = map.get(current);
            
            // 如果当前节点就是终点，直接返回累积乘积结果
            if (current.equals(end)) {
                return currentVal;
            }
            
            // 遍历当前节点连接的所有邻居节点
            for (Map.Entry<String, Double> neighbor : graph.get(current).entrySet()) {
                // k：当前邻居节点的名称（变量名）
                String k = neighbor.getKey();
                // v：从当前节点 current 到邻居节点 k 的边的权重
                double v = neighbor.getValue();
                
                // 如果该邻居节点已经在 map 中访问过，跳过避免死循环
                if (map.containsKey(k)) {
                    continue;
                }
                // 将邻居节点放入队列，等待后续探索
                queue.offer(k);
                // 记录从起点 start 到达邻居节点 k 的累积乘积值（当前累积值 * 当前边权重 v）
                map.put(k, currentVal * v);
            }
        }
        // 如果队列遍历完都没有找到终点，说明两点不可达，返回 -1.0
        return -1.0;
    }
}