# python hashmap and bfs ( a bit awkward)

• I thought I try a complicated method.

I first use hashmap to store the graph. each link represent the relative value of the two node.

Then use bfs to traverse the graph, and get the virtual value of each node.

I use variable "group" to indicate whether they have relation or not.

'''
from collections import deque

class Solution(object):
def calcEquation(self, equations, values, query):

``````    if len(equations) == 0:
return [ -1 for i in xrange(len(query))]

dic = {}
for i in xrange(len(equations)):
equation = equations[i]
v = values[i]
e1 = equation[0]
e2 = equation[1]

if e1 not in dic:
dic[e1] = []
dic[e1].append((e2,float(v)))

if e2 not in dic:
dic[e2] = []
if v != 0:
dic[e2].append((e1, 1.0 / float(v)))

res = {}

#bfs
group = 0
for k in dic:
if k not in res:
res[k] = (1,group)
q = deque([])
q.append(k)

while len(q) != 0:
cur = q.popleft()
for relative in dic[cur]:
if relative[0] not in res:
res[relative[0]] = (float(res[cur][0]) / float(relative[1]),group)
q.append(relative[0])

group += 1

ans = []
for q in query:
a = q[0]
b = q[1]
if a in res and b in res and res[a][1] == res[b][1]:
ans.append(float(res[a][0]) / float(res[b][0]))
else:
ans.append(-1)

return ans
``````

'''

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.