def calcEquation(equations, values, queries):
parent = {}
weight = {}
def find(x):
if x not in parent:
parent[x] = x
weight[x] = 1.0
if parent[x] != x:
origParent = parent[x]
parent[x] = find(parent[x])
weight[x] *= weight[origParent]
return parent[x]
def union(a, b, val):
rootA, rootB = find(a), find(b)
if rootA != rootB:
parent[rootA] = rootB
weight[rootA] = weight[b] * val / weight[a]
for (a, b), val in zip(equations, values):
union(a, b, val)
result = []
for a, b in queries:
if a not in parent or b not in parent:
result.append(-1.0)
elif find(a) != find(b):
result.append(-1.0)
else:
result.append(weight[a] / weight[b])
return result
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
$ curl repovive.com/roadmaps/data-structures/union-find/evaluate-division-solution
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████