Evaluate Division — Weighted Graph BFS/DFS

Problem

Given equations like A/B = k, answer queries like A/C. Return -1 if no path exists.

Approach — Weighted Graph BFS

Build directed weighted graph: A→B (k) and B→A (1/k). For each query, BFS multiplying edge weights.

Time: O(Q * (V+E)) | Space: O(V+E)

Solutions

Python

from collections import defaultdict, deque
class Solution:
    def calcEquation(self, equations: list[list[str]], values: list[float], queries: list[list[str]]) -> list[float]:
        adj=defaultdict(dict)
        for (a,b),v in zip(equations,values):
            adj[a][b]=v; adj[b][a]=1/v
        def bfs(src,dst):
            if src not in adj or dst not in adj: return -1
            if src==dst: return 1.0
            visited={src}; q=deque([(src,1.0)])
            while q:
                node,prod=q.popleft()
                if node==dst: return prod
                for nb,w in adj[node].items():
                    if nb not in visited:
                        visited.add(nb); q.append((nb,prod*w))
            return -1
        return [bfs(s,d) for s,d in queries]

Complexity

Time: O(Q * (V+E)) | Space: O(V+E)