**Solution**

**Evaluate Division** https://leetcode.com/problems/evaluate-division/

- Model the problem as a graph. a/b = 2.0 would be modelled as 2 nodes a and b and an edge from a to b as 2.0.
- Represent the graph as a dictionary of dictionary. graph[a] = {b:2.0} and graph[b] = {a:0.5}.
- Now solving any query x1/y1 is a dfs from x1 with terminal position y1 while multiplying the edge value along the way. Note that we design DFS method so that it returns True when the search is complete.
- Be careful about input like "x"/"x" - return False from DFS and return -1. Look at the code how we accomplish this.

```
class Solution(object):
def evaluate(self, graph, start, end, so_far, visited):
if start not in graph:
return False
elif start == end:
self.answer = so_far
return True
else:
visited.add(start)
candidates = (nbr for nbr in graph[start] if nbr not in visited)
for nbr in candidates:
if self.evaluate(graph, nbr, end, so_far*graph[start][nbr], visited):
return True
return False
def build_graph(self, equations, values):
graph = {}
for idx, equation in enumerate(equations):
x1, y1 = equation[0], equation[1]
graph.setdefault(x1, {})
graph.setdefault(y1, {})
graph[x1][y1],graph[y1][x1] = values[idx], 1.0/values[idx]
return graph
def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
graph = self.build_graph(equations, values)
result, self.answer = [], None
for query in queries:
answer = self.answer if self.evaluate(graph, query[0], query[1], 1.0, set([])) else -1
result.append(answer)
return result
```