Evaluate Division

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values,
                                vector<vector<string>>& queries) {
        unordered_map<string, unordered_map<string,double>> g;
        for (int i = 0; i < (int)equations.size(); ++i) {
            const string& a = equations[i][0];
            const string& b = equations[i][1];
            g[a][b] = values[i];
            g[b][a] = 1.0 / values[i];
        }
        auto query = [&](const string& src, const string& dst) -> double {
            if (!g.count(src) || !g.count(dst)) return -1.0;
            if (src == dst) return 1.0;
            unordered_set<string> seen{src};
            function<double(const string&, double)> dfs = [&](const string& node, double acc) -> double {
                if (node == dst) return acc;
                for (auto& [nx, w] : g[node]) {
                    if (seen.insert(nx).second) {
                        double r = dfs(nx, acc * w);
                        if (r >= 0) return r;
                    }
                }
                return -1.0;
            };
            return dfs(src, 1.0);
        };
        vector<double> ans;
        ans.reserve(queries.size());
        for (auto& q : queries) ans.push_back(query(q[0], q[1]));
        return ans;
    }
};

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
    g := map[string]map[string]float64{}
    for i, eq := range equations {
        a, b := eq[0], eq[1]
        if g[a] == nil {
            g[a] = map[string]float64{}
        }
        if g[b] == nil {
            g[b] = map[string]float64{}
        }
        g[a][b] = values[i]
        g[b][a] = 1.0 / values[i]
    }
    var dfs func(node, dst string, acc float64, seen map[string]bool) float64
    dfs = func(node, dst string, acc float64, seen map[string]bool) float64 {
        if node == dst {
            return acc
        }
        for nx, w := range g[node] {
            if !seen[nx] {
                seen[nx] = true
                r := dfs(nx, dst, acc*w, seen)
                if r >= 0 {
                    return r
                }
            }
        }
        return -1.0
    }
    query := func(src, dst string) float64 {
        if _, ok := g[src]; !ok {
            return -1.0
        }
        if _, ok := g[dst]; !ok {
            return -1.0
        }
        if src == dst {
            return 1.0
        }
        seen := map[string]bool{src: true}
        return dfs(src, dst, 1.0, seen)
    }
    ans := make([]float64, 0, len(queries))
    for _, q := range queries {
        ans = append(ans, query(q[0], q[1]))
    }
    return ans
}

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]:
        g = defaultdict(dict)
        for (a, b), v in zip(equations, values):
            g[a][b] = v
            g[b][a] = 1.0 / v

        def dfs(node: str, dst: str, acc: float, seen: set) -> float:
            if node == dst:
                return acc
            for nx, w in g[node].items():
                if nx not in seen:
                    seen.add(nx)
                    r = dfs(nx, dst, acc * w, seen)
                    if r >= 0:
                        return r
            return -1.0

        def query(src: str, dst: str) -> float:
            if src not in g or dst not in g:
                return -1.0
            if src == dst:
                return 1.0
            return dfs(src, dst, 1.0, {src})

        return [query(a, b) for a, b in queries]

function calcEquation(equations, values, queries) {
    const g = new Map();
    for (let i = 0; i < equations.length; i++) {
        const [a, b] = equations[i];
        if (!g.has(a)) g.set(a, new Map());
        if (!g.has(b)) g.set(b, new Map());
        g.get(a).set(b, values[i]);
        g.get(b).set(a, 1.0 / values[i]);
    }
    const dfs = (node, dst, acc, seen) => {
        if (node === dst) return acc;
        for (const [nx, w] of g.get(node)) {
            if (!seen.has(nx)) {
                seen.add(nx);
                const r = dfs(nx, dst, acc * w, seen);
                if (r >= 0) return r;
            }
        }
        return -1.0;
    };
    const query = (src, dst) => {
        if (!g.has(src) || !g.has(dst)) return -1.0;
        if (src === dst) return 1.0;
        return dfs(src, dst, 1.0, new Set([src]));
    };
    return queries.map(([a, b]) => query(a, b));
}

class Solution {
    private Map<String, Map<String, Double>> g;

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        g = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            String a = equations.get(i).get(0);
            String b = equations.get(i).get(1);
            g.computeIfAbsent(a, k -> new HashMap<>()).put(b, values[i]);
            g.computeIfAbsent(b, k -> new HashMap<>()).put(a, 1.0 / values[i]);
        }
        double[] ans = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            ans[i] = query(queries.get(i).get(0), queries.get(i).get(1));
        }
        return ans;
    }

    private double query(String src, String dst) {
        if (!g.containsKey(src) || !g.containsKey(dst)) return -1.0;
        if (src.equals(dst)) return 1.0;
        Set<String> seen = new HashSet<>();
        seen.add(src);
        return dfs(src, dst, 1.0, seen);
    }

    private double dfs(String node, String dst, double acc, Set<String> seen) {
        if (node.equals(dst)) return acc;
        for (Map.Entry<String, Double> e : g.get(node).entrySet()) {
            if (seen.add(e.getKey())) {
                double r = dfs(e.getKey(), dst, acc * e.getValue(), seen);
                if (r >= 0) return r;
            }
        }
        return -1.0;
    }
}

function calcEquation(equations: string[][], values: number[], queries: string[][]): number[] {
    const g = new Map<string, Map<string, number>>();
    for (let i = 0; i < equations.length; i++) {
        const [a, b] = equations[i];
        if (!g.has(a)) g.set(a, new Map());
        if (!g.has(b)) g.set(b, new Map());
        g.get(a)!.set(b, values[i]);
        g.get(b)!.set(a, 1.0 / values[i]);
    }
    const dfs = (node: string, dst: string, acc: number, seen: Set<string>): number => {
        if (node === dst) return acc;
        for (const [nx, w] of g.get(node)!) {
            if (!seen.has(nx)) {
                seen.add(nx);
                const r = dfs(nx, dst, acc * w, seen);
                if (r >= 0) return r;
            }
        }
        return -1.0;
    };
    const query = (src: string, dst: string): number => {
        if (!g.has(src) || !g.has(dst)) return -1.0;
        if (src === dst) return 1.0;
        return dfs(src, dst, 1.0, new Set<string>([src]));
    };
    return queries.map(([a, b]) => query(a, b));
}