Evaluate Division solution and explanation

from collections import defaultdict

def calcEquation(equations, values, queries):
    graph = defaultdict(dict)
    
    # Build the graph
    for (dividend, divisor), value in zip(equations, values):
        graph[dividend][divisor] = value
        graph[divisor][dividend] = 1 / value
    
    def dfs(start, end, visited, value):
        if start == end:
            return value
        visited.add(start)

        for neighbor, weight in graph[start].items():
            if neighbor not in visited:
                result = dfs(neighbor, end, visited, value * weight)
                if result is not None:
                    return result
                
        return None

    results = []
    for dividend, divisor in queries:
        if dividend not in graph or divisor not in graph:
            results.append(-1.0)
        else:
            visited = set()
            result = dfs(dividend, divisor, visited, 1)
            results.append(result if result is not None else -1.0)

    return results

function calcEquation(equations, values, queries) {
    const graph = new Map();

    // Build the graph
    equations.forEach(([start, end], i) => {
        if (!graph.has(start)) graph.set(start, new Map());
        if (!graph.has(end)) graph.set(end, new Map());
        graph.get(start).set(end, values[i]);
        graph.get(end).set(start, 1 / values[i]);
    });

    function dfs(start, end, visited, product) {
        if (!graph.has(start)) return -1.0;

        if (start === end) return product;

        visited.add(start);

        const neighbors = graph.get(start);
        for (const [next, value] of neighbors) {
            if (!visited.has(next)) {
                const result = dfs(next, end, visited, product * value);
                if (result !== -1.0) return result;
            }
        }

        visited.delete(start);
        return -1.0;
    }

    return queries.map(([dividend, divisor]) => {
        return dfs(dividend, divisor, new Set(), 1.0);
    });
}

import java.util.*;

class Solution {
    class Node {
        String parent;
        double ratio;
        Node(String parent, double ratio) {
            this.parent = parent;
            this.ratio = ratio;
        }
    }

    private Map<String, Node> parents = new HashMap<>();

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        for (int i = 0; i < equations.size(); i++) {
            List<String> equation = equations.get(i);
            String dividend = equation.get(0);
            String divisor = equation.get(1);
            double quotient = values[i];
            union(dividend, divisor, quotient);
        }

        double[] result = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            List<String> query = queries.get(i);
            String dividend = query.get(0);
            String divisor = query.get(1);
            if (!parents.containsKey(dividend) || !parents.containsKey(divisor)) {
                result[i] = -1.0;
            } else {
                Node rootDividend = find(dividend);
                Node rootDivisor = find(divisor);
                if (!rootDividend.parent.equals(rootDivisor.parent)) {
                    result[i] = -1.0;
                } else {
                    result[i] = rootDividend.ratio / rootDivisor.ratio;
                }
            }
        }
        return result;
    }

    private Node find(String string) {
        if (!parents.containsKey(string)) {
            parents.put(string, new Node(string, 1.0));
        }
        Node currentNode = parents.get(string);
        if (!currentNode.parent.equals(string)) {
            Node parentNode = find(currentNode.parent);
            parents.put(string, new Node(parentNode.parent, currentNode.ratio * parentNode.ratio));
        }
        return parents.get(string);
    }

    private void union(String dividend, String divisor, double quotient) {
        Node rootDividend = find(dividend);
        Node rootDivisor = find(divisor);
        if (!rootDividend.parent.equals(rootDivisor.parent)) {
            parents.put(rootDividend.parent, new Node(rootDivisor.parent, quotient * rootDivisor.ratio / rootDividend.ratio));
        }
    }
}

#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<double> calcEquation(
        vector<vector<string>>& equations, 
        vector<double>& values, 
        vector<vector<string>>& queries) {

        unordered_map<string, pair<string, double>> parents;

        // Find function with path compression
        function<pair<string, double>(string)> find = [&](string v) {
            if (!parents.count(v)) return make_pair(v, 1.0);
            auto& [p, w] = parents[v];
            if (v != p) {
                auto result = find(p);
                parents[v] = {result.first, w * result.second};
            }
            return parents[v];
        };

        // Union function
        auto unite = [&](string v1, string v2, double ratio) {
            auto [root1, weight1] = find(v1);
            auto [root2, weight2] = find(v2);
            
            if (root1 != root2) {
                parents[root2] = {root1, ratio * weight1 / weight2};
            }
        };

        for (int i = 0; i < equations.size(); ++i) {
            const auto& eq = equations[i];
            unite(eq[0], eq[1], values[i]);
        }

        vector<double> results;
        for (const auto& query : queries) {
            if (!parents.count(query[0]) || !parents.count(query[1])) {
                results.push_back(-1.0);
                continue;
            }

            auto [root1, weight1] = find(query[0]);
            auto [root2, weight2] = find(query[1]);

            if (root1 != root2) {
                results.push_back(-1.0);
            } else {
                results.push_back(weight1 / weight2);
            }
        }

        return results;
    }
};

function calcEquation(equations: string[][], values: number[], queries: string[][]): number[] {
    const g: Record<string, [string, number][]> = {};
    const ans = Array.from({ length: queries.length }, () => -1);

    for (let i = 0; i < equations.length; i++) {
        const [a, b] = equations[i];
        (g[a] ??= []).push([b, values[i]]);
        (g[b] ??= []).push([a, 1 / values[i]]);
    }

    for (let i = 0; i < queries.length; i++) {
        const [c, d] = queries[i];
        const vis = new Set<string>();
        const q: [string, number][] = [[c, 1]];

        if (!g[c] || !g[d]) continue;
        if (c === d) {
            ans[i] = 1;
            continue;
        }

        for (const [current, v] of q) {
            if (vis.has(current)) continue;
            vis.add(current);

            for (const [intermediate, multiplier] of g[current]) {
                if (vis.has(intermediate)) continue;

                if (intermediate === d) {
                    ans[i] = v * multiplier;
                    break;
                }

                q.push([intermediate, v * multiplier]);
            }

            if (ans[i] !== -1) break;
        }
    }

    return ans;
}

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	p := make(map[string]string)
	w := make(map[string]float64)
	for _, e := range equations {
		a, b := e[0], e[1]
		p[a], p[b] = a, b
		w[a], w[b] = 1.0, 1.0
	}

	var find func(x string) string
	find = func(x string) string {
		if p[x] != x {
			origin := p[x]
			p[x] = find(p[x])
			w[x] *= w[origin]
		}
		return p[x]
	}

	for i, v := range values {
		a, b := equations[i][0], equations[i][1]
		pa, pb := find(a), find(b)
		if pa == pb {
			continue
		}
		p[pa] = pb
		w[pa] = w[b] * v / w[a]
	}
	var ans []float64
	for _, e := range queries {
		c, d := e[0], e[1]
		if p[c] == "" || p[d] == "" || find(c) != find(d) {
			ans = append(ans, -1.0)
		} else {
			ans = append(ans, w[c]/w[d])
		}
	}
	return ans
}

use std::collections::HashMap;

#[derive(Debug)]
pub struct DSUNode {
    parent: String,
    weight: f64,
}

pub struct DisjointSetUnion {
    nodes: HashMap<String, DSUNode>,
}

impl DisjointSetUnion {
    pub fn new(equations: &Vec<Vec<String>>) -> DisjointSetUnion {
        let mut nodes = HashMap::new();
        for equation in equations.iter() {
            for iter in equation.iter() {
                nodes.insert(
                    iter.clone(),
                    DSUNode {
                        parent: iter.clone(),
                        weight: 1.0,
                    },
                );
            }
        }
        DisjointSetUnion { nodes }
    }

    pub fn find(&mut self, v: &String) -> String {
        let origin = self.nodes[v].parent.clone();
        if origin == *v {
            return origin;
        }

        let root = self.find(&origin);
        self.nodes.get_mut(v).unwrap().parent = root.clone();
        self.nodes.get_mut(v).unwrap().weight *= self.nodes[&origin].weight;
        root
    }

    pub fn union(&mut self, a: &String, b: &String, v: f64) {
        let pa = self.find(a);
        let pb = self.find(b);
        if pa == pb {
            return;
        }
        let (wa, wb) = (self.nodes[a].weight, self.nodes[b].weight);
        self.nodes.get_mut(&pa).unwrap().parent = pb;
        self.nodes.get_mut(&pa).unwrap().weight = (wb * v) / wa;
    }

    pub fn exist(&mut self, k: &String) -> bool {
        self.nodes.contains_key(k)
    }

    pub fn calc_value(&mut self, a: &String, b: &String) -> f64 {
        if !self.exist(a) || !self.exist(b) || self.find(a) != self.find(b) {
            -1.0
        } else {
            let wa = self.nodes[a].weight;
            let wb = self.nodes[b].weight;
            wa / wb
        }
    }
}

impl Solution {
    pub fn calc_equation(
        equations: Vec<Vec<String>>,
        values: Vec<f64>,
        queries: Vec<Vec<String>>,
    ) -> Vec<f64> {
        let mut dsu = DisjointSetUnion::new(&equations);
        for (i, &v) in values.iter().enumerate() {
            let (a, b) = (&equations[i][0], &equations[i][1]);
            dsu.union(a, b, v);
        }

        let mut ans = vec![];
        for querie in queries {
            let (c, d) = (&querie[0], &querie[1]);
            ans.push(dsu.calc_value(c, d));
        }
        ans
    }
}