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.

&nbsp;
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]


&nbsp;
Constraints:


	1 &lt;= equations.length &lt;= 20
	equations[i].length == 2
	1 &lt;= Ai.length, Bi.length &lt;= 5
	values.length == equations.length
	0.0 &lt; values[i] &lt;= 20.0
	1 &lt;= queries.length &lt;= 20
	queries[i].length == 2
	1 &lt;= Cj.length, Dj.length &lt;= 5
	Ai, Bi, Cj, Dj consist of lower case English letters and digits.


class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = dict()
        
        for (n, d), v in zip(equations, values):
            if n not in graph:
                graph[n] = []
            if d not in graph:
                graph[d] = []
                
            graph[n].append((d, v))
            graph[d].append((n, 1/v))
        
        def dfs(node, target, product, visited):
            if n not in graph or d not in graph:
                return -1
            
            if node == target:
                return product
            
            visited.add(node)
            
            for neighbor, quotient in graph[node]:
                if neighbor not in visited:
                    soln = dfs(neighbor, target, product * quotient, visited)
                    if soln != -1:
                        return soln
                    
            return -1
        
        solns = []
        for n, d in queries:
            solns.append(dfs(n, d, 1, set()))
            
        return solns
class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int len = equations.size();
        Map<String, Integer> varMap = new HashMap<>();
        int varCnt = 0;
        for (int i = 0; i < len; i++) {
            if (!varMap.containsKey(equations.get(i).get(0))) {
                varMap.put(equations.get(i).get(0), varCnt++);
            }
            if (!varMap.containsKey(equations.get(i).get(1))) {
                varMap.put(equations.get(i).get(1), varCnt++);
            }
        }

        List<Pair>[] edges = new List[varCnt];
        for (int i = 0; i < varCnt; i++) {
            edges[i] = new ArrayList<>();
        }

        for (int i = 0; i < len; i++) {
            int va = varMap.get(equations.get(i).get(0));
            int vb = varMap.get(equations.get(i).get(1));
            edges[va].add(new Pair(vb, values[i]));
            edges[vb].add(new Pair(va, 1.0 / values[i]));
        }

        int queriesCnt = queries.size();
        double[] ans = new double[queriesCnt];
        for (int i = 0; i < queriesCnt; i++) {
            List<String> query = queries.get(i);
            double result = -1.0;
            if (varMap.containsKey(query.get(0)) && varMap.containsKey(query.get(1))) {
                int idxA = varMap.get(query.get(0));
                int idxB = varMap.get(query.get(1));
                if (idxA == idxB) {
                    result = 1.0;
                } else {
                    Queue<Integer> points = new LinkedList<>();
                    points.offer(idxA);
                    double[] ratios = new double[varCnt];
                    Arrays.fill(ratios, -1.0);
                    ratios[idxA] = 1.0;
                    while (!points.isEmpty() && ratios[idxB] < 0) {
                        int cur = points.poll();
                        for (Pair pair : edges[cur]) {
                            int y = pair.index;
                            double value = pair.value;
                            if (ratios[y] < 0) {
                                ratios[y] = ratios[cur] * value;
                                points.offer(y);
                            }
                        }
                    }

                    result = ratios[idxB];
                }
            }

            ans[i] = result;
        }

        return ans;
    }

    class Pair {
        int index;
        double value;

        public Pair(int index, double value) {
            this.index = index;
            this.value = value;
        }
    }
}
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        map<string, vector<pair<string, double>>> graph;
		map<string, double> dist;
        map<string, bool> visited;
        for(int i=0;i<equations.size();i++){
            if(graph.count(equations[i][0])==0){
                graph[equations[i][0]] = {};
				visited[equations[i][0]] = false;
                dist[equations[i][0]] = DBL_MAX;
            }
            if(graph.count(equations[i][1])==0){
                graph[equations[i][1]] = {};
				dist[equations[i][0]] = DBL_MAX;
            }
            graph[equations[i][0]].push_back({equations[i][1], values[i]});
            if(values[i]!=0)
                graph[equations[i][1]].push_back({equations[i][0], 1/values[i]});
            else
                graph[equations[i][1]].push_back({equations[i][0], -1});
        }
        vector<double> result;
        for(int i=0;i<queries.size();i++){
            if(graph.count(queries[i][0])==0 || graph.count(queries[i][1])==0){
                result.push_back(-1);
                continue;
            }
            if(queries[i][0] == queries[i][1]){
                result.push_back(1);
                continue;
            }
            for(auto j: visited)
                visited[j.first] = false;
            priority_queue<pair<double, string>, vector<pair<double, string>>, greater<pair<double, string>>> pq;
            dist[queries[i][0]] = 1;;
            pq.push({1, queries[i][0]});
            bool flag=false;
            while(!pq.empty()){
                auto k = pq.top();
                pq.pop();
                visited[k.second] = true;
                if(k.second==queries[i][1]){
                    flag=true;
                    result.push_back(dist[k.second]);
                    break;
                }
                for(int j=0;j<graph[k.second].size();j++){
                    if(!visited[graph[k.second][j].first])
                    {dist[graph[k.second][j].first] = dist[k.second] * graph[k.second][j].second;
                    pq.push({dist[graph[k.second][j].first], graph[k.second][j].first});}
                }
            }
            if(!flag)
                result.push_back(-1);
        }
        return result;
    }
};
var calcEquation = function(equations, values, queries) {
    const res = []
    
    for(let i = 0; i < queries.length; i++) {
        const currQuery = queries[i]
        
        const [currStart, currDestination] = currQuery
        
        const adj = {}
        
        const additionalEdges = []
        const additionalValues = []
        
        const visited = new Set()
        
        equations.forEach((el,idx) => {
            const [to, from] = el
            const val = values[idx]
            
            additionalEdges.push([from, to])
            additionalValues.push(1/val)
        })
        
        values = [...values, ...additionalValues]
        let idx = 0
        for(const [from, to] of [...equations, ...additionalEdges]) {
            if(!(from in adj)) adj[from] = []
            
            adj[from].push([to, values[idx]])
            
            idx++
        }
        
        if(!(currStart in adj) || !(currDestination in adj)) {
            res.push(-1)
            continue
        }
        
        if(currStart === currDestination) {
            res.push(1)
            continue
        }
        
        
        let currEvaluation = 1
        let found = false
        const subResult = dfs(currStart)
        if(!found) res.push(-1)
        
        
        
        function dfs(node) {
            if(!node) return null
            if(node === currDestination) {
                return true
            }
            
            const children = adj[node] // [ [to, val] ]
            
            if(!children) return false
            
            for(const child of children) {
                if(visited.has(node)) continue
                visited.add(node)
                
                currEvaluation =  currEvaluation*child[1]

                if(dfs(child[0]) === true) {
                    !found && res.push(currEvaluation)
                    found = true
                   return 
                }
                visited.delete(node)
                currEvaluation /= child[1]
            }
        }
        
        }
    return res
};
Evaluate Division