# Simple'n'Clean DFS solution in Python

• A series of equations `A / B = k` can be seen as a graph in which nodes are the dividend and divisor A and B and weights are the result of the division. So we simply create the graph and traverse it with DFS/BFS to get our result.

Complexity is `K * O(N + M)` where N and M are the number of nodes and edges, and `K` is the number of queries. How many nodes can we have? It's `2 * E`, where `E` is the number of equations (2 different nodes per each equation). We can have at most `E` edges in the graph.

So total complexity is `O(K * E)`, with `O(E)` additional space for the graph.

``````class Solution(object):
def calcEquation(self, equations, values, queries):

def dfs(start, end, path, paths):
if start == end and start in G:
paths[0] = path
return
if start in vis:
return
for node in G[start]:
dfs(node, end, path * W[start, node], paths)

G, W = collections.defaultdict(set), collections.defaultdict(float)
for (A, B), V in zip(equations, values):
G[A], G[B] = G[A] | {B}, G[B] | {A}
W[A, B], W[B, A] = V, 1.0 / V

res = []
for X, Y in queries:
paths, vis = [-1.0], set()
dfs(X, Y, 1.0, paths)
res += paths[0],
return res
``````

• I like your code! Clean and easy to understand.

• I am new to python, and I am not very familiar with python bitwise operator. So how the operator "|" works here.
Thank you.

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