# Python Disjoint Sets: Easy enough

• ``````class Solution(object):
class Node(object):
def __init__(self, var):
self.var = var
self.par = None
self.val = 1.0

def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
m = {}
for i, eq in enumerate(equations):
n, d = eq[0], eq[1]
if n in m: nid, nm = self.find(n, m)
else:
m[n], nm = self.Node(n), 1.0
nid = m[n]
if d in m: did, dm = self.find(d, m)
else:
m[d], dm = self.Node(n), 1.0
did = m[d]
if did == nid: continue
did.val = (1 / values[i]) * (nm/dm)
did.par = nid
res = []
for q in queries:
n, d = q[0], q[1]
if n not in m:
res.append(-1.0)
continue
if d not in m:
res.append(-1.0)
continue
n, num = self.find(n, m)
d, den = self.find(d, m)
if n != d:
res.append(-1.0)
continue
res.append(num / den)
return res

def find(self, v, m):
if m[v].par == None: return m[v], 1.0
par, mult = self.find(m[v].par.var, m)
m[v].val *= mult
m[v].par = par
return par, m[v].val
``````

Logic: When you connect yourself to the set representative, multiply the current value of the node in the path to that of parent's.
In short, if hypothetically a<-b<-c<-d exists (a is the set rep), with 1, 2, 3, 4 (which conveys that b = 2a; c = 3b; d = 4c) values, and you do d/e=5, then d is connected to 'a' directly and attached values become 1, 2, 6, 24 respectively (which conveys that b = 2a; c = 6a; d = 24a) and all the nodes are directly connected to a.

• Awesome solution \m/

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