---
# System prepended metadata

title: Untitled

---

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.

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.

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 ]

// No x returns -1
// a / c = (a / b) * (b / c) = 2 * 3 = 6
// c / a = (c / b) * (b / a) = 1/3 * 1/2

// 1. Construct the undirected graph
// graph: a: b, 2
//        b: a, 1/2 c, 3
          c: b, 1/3
          
numerator: a
denominator: c

// 
// seen = a, b, 
// queue: c
// 
// num = 6

|V| = number of letters appeared in eqations
|E|: number of edges. e.g. a / b -> edge, b / c -> edge -> 2
Time: O(|V| + |E|) + O(|queries| == n * |edges|)
a -> b -> c

Space: O(|letters in equation|)

```java=
public float divide(List<String[]> equations, float[] values, List<String[]> queries) {
    // 1. Construct the graph
    Map<String, Map<String, Integer>> graph = new HashMap<>(); // {a, {b, 2}} := a / b = 2
    for (int i = 0; i < equations.length; i++) {
        String[] equation = equations.get(i);
        float value = values[i];
        String numerator = equation[0]; // a
        String denominator = equation[1]; // b
        graph.putIfAbsent(numerator, new HashMap<>());
        graph.get(numerator).put(denominator, value);
        graph.putIfAbsent(denominator, new HashMap<>());
        graph.get(denominator).put(numerator, 1.0 / value);
    }
    
    List<Float> ans = new ArrayList<>();
    for (String[] query : queries) {
        String numerator = query[0]; // a
        String denominator = query[1]; // c
        float value = diviser(graph, numerator, denominator); // 6
        ans.add(value);
    }
    
    return ans;
}
                        
private float diviser(final Map<String, Map<String, Integer>> graph, String numerator, String denominator) {
    if (numerator.equals(demonitor)) {
        return 1.0;
    }
    
    Set<String> seen = new HashSet<>();
    seen.add(numerator); // a, b
    Queue<Pair<String, Integer>> queue = new ArrayDeque<>(); // {b, 2}
    queue.add(new Pair(numerator, 1));
    
    if (!graph.containsKey(numerator) || !graph.containsKey(denominator)) {
        return -1.0;
    }
    
    while (!queue.isEmpty()) {
        int size = queue.size(); // 1
        for (int i = 0; i < size; i++) {
            Pair<String, Integer> curr = queue.poll(); // {b, 2}
            int num = curr.getValue(); // 2
            for (String neighbor : graph.get(curr.getKey()).keySet()) { // c
                if (seen.contains(neighbor)) {
                    continue;
                }
                if (neighbor.equals(denominator)) {
                    return num * graph.get(curr.getKey()).get(neighbor); // return 2 * 3 = 6
                }
                queue.add(new Pair(neighbor, num * graph.get(numerator).get(neighbor)));
                seen.add(neighbor);
            }
        }
    }
    
    return -1.0;
}
    
```