Evaluate Division

Intuition

Solution

class Graph:
    def __init__(self, size):
        self.size = size
        self.adj = [[] for _ in range(size)]

    def add_edge(self, p, q, value):
        self.adj[p].append((q, value))
        self.adj[q].append((p, 1 / value))


class ConnectedComponentsWithValue:
    def __init__(self, graph):
        self.id = [-1] * graph.size
        self.values = [1.0] * graph.size
        self.count = 0
        self.visited = [False] * graph.size

        for vertex in range(graph.size):
            if not self.visited[vertex]:
                self.dfs(graph, vertex, 1)
                self.count += 1

    def dfs(self, graph, vertex, value):
        self.visited[vertex] = True
        self.values[vertex] = value
        self.id[vertex] = self.count
        for child, div in graph.adj[vertex]:
            if not self.visited[child]:
                self.dfs(graph, child, value / div)

    def connected(self, p, q):
        return self.id[p] == self.id[q]


class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        chars = set()
        for x, y in equations:
            chars.add(x)
            chars.add(y)
        chars = list(chars)

        ids = {}
        for i, c in enumerate(chars):
            ids[c] = i

        graph = Graph(len(chars))
        for (x, y), v in zip(equations, values):
            graph.add_edge(ids[x], ids[y], v)

        components = ConnectedComponentsWithValue(graph)
        ans = []
        for x, y in queries:
            if x not in ids or y not in ids:
                ans.append(-1)
            elif x == y:
                ans.append(1)
            elif components.connected(ids[x], ids[y]):
                ans.append(components.values[ids[x]] / components.values[ids[y]])
            else:
                ans.append(-1)
        return ans