calculateEquation

/**
 * 
 * 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 equation Ai / 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.} equations 
 * @param {*} values 
 * @param {*} queries 
 * @returns 
 */
export default function calcEquation(
  equations,
  values,
  queries,
) {
  const graph = new Map();

  function addEdge(from, to, weight) {
    if (!graph.has(from)) {
      graph.set(from, []);
    }

    graph.get(from)!.push([to, weight]);
  }

  // Build graph
  for (let i = 0; i < equations.length; i++) {
    const [a, b] = equations[i];
    const value = values[i];

    // a / b = value
    addEdge(a, b, value);

    // b / a = 1 / value
    addEdge(b, a, 1 / value);
  }

  function dfs(
    current,
    target,
    visited,
    product
  ) {
    if (current === target) {
      return product;
    }

    visited.add(current);

    const neighbors = graph.get(current) ?? [];

    for (const [next, weight] of neighbors) {
      if (visited.has(next)) {
        continue;
      }

      const result = dfs(next, target, visited, product * weight);

      if (result !== -1.0) {
        return result;
      }
    }

    return -1.0;
  }

  // array of numbers
  const result = [];

  for (const [source, target] of queries) {
    // Undefined variables cannot produce a valid answer.
    if (!graph.has(source) || !graph.has(target)) {
      result.push(-1.0);
      continue;
    }

    result.push(dfs(source, target, new Set(), 1.0));
  }

  return result;
}