# 399. Evaluate Division

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i]represent the equationAi / Bi = values[i]`. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

# Solution

Approach 1: use the idea of Union Find. The key to this problem is how to figure out whether two variables are connected. It can be done with a search (dfs/bfs), but union find is asymptotically faster, since it compresses paths to the root.

# Code (Python)

Approach 1:

Approach 2:

# Code (C++)

Approach 1:

Approach 2:

# Code (Typescript)

Approach 1:

function calcEquation(equations: string[][], values: number[], queries: string[][]): number[] {
    // The key to this problem is how to figure out whether two variables are 'connected'. 
    // It can be done with a search (dfs/bfs), but union find is asymptotically faster,
    // since it compresses paths to the root, so tree is shallow.

    // stores {node: [root, weight]}
    const parent: { [key: string]: [string, number] } = {}; 

    // finds the root, and ratio of nodeValue / rootValue
    function findRoot(node: string): [string, number] {
        // base case: root is self
        if (!(node in parent)) {
            parent[node] = [node, 1];
            return parent[node];
        }
        // recursive case: flatten the path so that parent[node] is the root for all nodes along the path
        const [immediateParent, parentWeight] = parent[node];
        if (immediateParent !== node) {
            const [root, weight] = findRoot(immediateParent);
            parent[node] = [root, weight * parentWeight];
        }
        return parent[node]
    }

    for (let i = 0; i < equations.length; i++) {
        let [numerator, denominator] = equations[i];
        let [numeratorRoot, numeratorWeight] = findRoot(numerator);
        let [denominatorRoot, denominatorWeight] = findRoot(denominator);
        // if they're in the same group, should really check for consistency, but this problem guarantees consistency
        if (numeratorRoot !== denominatorRoot) {
            // merge two groups by connecting one group's root to another group's root
            parent[numeratorRoot] = [denominatorRoot, denominatorWeight * values[i] / numeratorWeight];
        }
    }  

    const result = [];
    for (let [node1, node2] of queries) {
        if (!parent[node1] || !parent[node2]) {
            result.push(-1);
        } else if (node1 === node2) {
            result.push(1);
        } else {
            let [root1, weight1] = findRoot(node1);
            let [root2, weight2] = findRoot(node2);
            if (root1 !== root2) {
                result.push(-1);
            } else {
                result.push(weight1 / weight2);
            }
        }
    }
    
    return result;
};