399

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        adjacency = defaultdict(set)
        costs = {}

        def add(a, b, v):
            if a == b:
                return

            costs[(a, b)] = v
            costs[(b, a)] = 1.0 / v
            adjacency[a].add(b)
            adjacency[b].add(a)


        for (a, b), v in zip(equations, values):
            add(a, b, v)


        def calc(a: str, b: str) -> float:
            if a == b and a in adjacency.keys():
                return 1.0

            if (a, b) in costs.keys():
                return costs[(a, b)]

            q = deque(
                (x, costs[(a, x)])
                for x in adjacency[a]
            )  # Contains all a / x values we've discovered

            seen = set()
            while q:
                cur_x, cur_val = q.popleft()
                if cur_x in seen:
                    continue
                seen.add(cur_x)

                for next_x in adjacency[cur_x]:
                    if next_x in seen:
                        continue

                    next_val = cur_val * costs[(cur_x, next_x)]
                    if next_x == b:
                        return next_val
                    q.append((next_x, next_val))

            return -1.0


        return [calc(a, b) for a, b in queries]