LC399 Evaluate Division

"""
main idea: transform a/b=k1, b/c=k2 to a ===(cost:k1 )==> b ==(cost:k2)=> c   for query a/c question, convert it into find the shortest cost from a to c. The cost is k1 * k2
step1: build a two dimensional graph in the form of adjacency list.Dividend is key , divisor and cost are  stored in the form of pairs. In a way divisor acts as dividend's neighber.  
step2: start from dividend with cost of 1.0, traverse all the neighbours of dividend. 
step3: pop out first stop from queue, compare if cur_divisor is same of target_divisor from query.
if target_divisor is same as cur_divisor, means the traversal starting from target_dividend has found divisor;
if not found, push current new divisor and cost so far into queue.
step4: Each time a divisor is visited, save it in the set to prevent repeated multiplication.
step5: visited all the neighbours of possible divisor on the way of traversal, updating queue  until queue is empty. it means target divisor is not found. return -1.0
"""
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        # time O(m(p+n)) ~ O(N^2) where m : query #, p: equation #, n: val #
        # e.g. x/y = val  
        graph = {}
        def build_graph(equations,values):
            def add_edge(x,y,val):
                if x not in graph:
                    graph[x] = [(y,val)]
                else:
                    graph[x].append((y,val))
            for (x,y),val in zip(equations,values):
                add_edge(x,y,val)
                add_edge(y,x,1/val)

        def find_path(query):
            # a/ b
            a, b = query
            if a not in graph or b not in graph:
                return -1.0
            
            q = collections.deque([(a,1.0)])
            seen = set()
            
            while q:
                y, val_cur = q.popleft()
                # a/a = 1.0
                if b == y:
                    return val_cur
                # check all nodes connected  with x 
                seen.add(y)
                for y_neighbour,val in graph[y]:
                    if y_neighbour not in seen:
                        q.append((y_neighbour,val*val_cur))
            return -1.0
        
        build_graph(equations,values)
        return [find_path(q) for q in queries]                         

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        # time O(V^3)
        quot = collections.defaultdict(dict)
        for (num,dev),val in zip(equations,values):
            quot[num][num] = quot[dev][dev] = 1.0
            quot[num][dev] = val
            quot[dev][num] = 1/val
        for k in quot:
            for i in quot[k]:
                for j in quot[k]:
                    quot[i][j] = quot[i][k]*quot[k][j]
        return [quot[num].get(dev,-1.0) for num,dev in queries]