## 399. Evaluate Division

Equations are given in the formatA / B = k, whereAandBare variables represented as strings, andkis a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return-1.0.

Example:
Givena / 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 ].

The input is:vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries, whereequations.size() == values.size(), and the values are positive. This represents the equations. Returnvector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

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

Thoughts:

1. Explicity building adj list: for permutation of all the pairs of neighbors in one's node i , j, calculate the i , j value as q[i][k] * q[k][j]: assume q[i][i] = 1
2. Union Find
3. DFS

Code: Building adj list: T: O(n^3), S:(n^2)

class Solution(object):
def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
q = collections.defaultdict(dict)

# build the graph by building the adj list
for (a, b) , val in zip(equations, values):
# identity
q[a][a] = q[b][b] = 1.0
q[a][b] = val
q[b][a] = 1/val

for k in q:
for i in q[k]:
for j in q[k]:
q[i][j] = q[i][k] * q[k][j] # connecting nodes explicitly

return [q[a].get(b, -1.0) for a , b in queries]

Code: DFS + Hash

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

for (int i = 0 ; i < values.size(); i++){
}

for (auto q: queries){
unordered_set<string> s;
double tmp = dfs(adj, s, q.first, q.second);
if(tmp) res.push_back(tmp);
else res.push_back(-1);
}

return res;
}

private:
double dfs(unordered_map<string, unordered_map<string, double>>& adj, unordered_set<string>& s,
string a, string b){

if(s.find(n.first) == s.end()){
s.insert(n.first);
double tmp =  dfs(adj, s, n.first, b);
if (tmp) return n.second * tmp;
}
}

return 0; // did not find
}

};

Code: Union Find

class Solution(object):
def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
def union(n1, n2, val):
p1, p2 = find(n1), find(n2)
r = n2.value * val / n1.value # v(n1) * val = v(n2) * r , r = v(n1) * val / v(n2)

# doing the reverse linear searching for p1's child in the map, normalize the value
for entry in m.values():
if find(entry) == p1:
entry.value *= r
p1.parent = p2

def find(node):
while node.parent!= node:
# node.parent = node.parent.parent
node = node.parent
return node

m, res = {}, []

for i, (a , b) in enumerate(equations):
value = values[i]
if a not in m and b not in m:
node_a, node_b = Node(), Node()
node_a.value = value
node_a.parent = node_b
node_b.value = 1
m[a] = node_a
m[b] = node_b

elif a not in m:
node_a = Node()
node_a.value = m[b].value * value
node_a.parent = m[b]
m[a] = node_a

elif b not in m:
node_b = Node()
node_b.value = m[a].value / value
node_b.parent = m[a] # order switched
m[b] = node_b

else:
union(m[a], m[b], value)

for a, b in queries:
if a not in m or b not in m or find(m[a]) != find(m[b]):
res.append(-1)

else:
res.append(m[a].value/m[b].value)

return res

class Node(object):
def __init__ (self):
self.parent = self
self.value = 0