Python Disjoint Sets: Easy enough


  • 1
    G
    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.


  • 0
    A

    Awesome solution \m/


Log in to reply
 

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