# Python graph + dfs search

• ``````from collections import defaultdict

class Solution(object):

def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
# adjacency list graph G, G[v1] --> [(v2, w12), (v3, w13)...]
# where w12 is the weight for a directed edge v1->v2, where v1 / v2 = w12
G = defaultdict(list)
for (v1, v2), val in zip(equations, values):
# v1 / v2 = val
G[v1].append((v2, val))
G[v2].append((v1, 1 / val))

# for each query v1 / v2, check whether there is a path from v1 to v2
# if so, the result of v1 / v2 is given by the accumulated product of
# all weights on the path
results = []
for v1, v2 in queries:
if v1 in G and v2 in G:
results.append(self.check_path(G, v1, v2))
else:   # if either of v1 and v2 doesn't exist in the graph
results.append(-1.0)
return results

def check_path(self, G, v1, v2):
visited = set()
weight_path = []

def backtrack(v):   # dfs with backtracking to find a path v --> v2
if v == v2:
return True
for x, w in G[v]:
if x not in visited:
weight_path.append(w)
if backtrack(x):
return True
del weight_path[-1]  # elimination to restore the original path
return False

if backtrack(v1):
r = 1.0
for w in weight_path:
r *= w
return r
return -1.0``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.