Rewrite the code using Graph class and ConnectedComponents methods
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