Evaluate Division

This approach is the same as the previous approach, but in this approach, we will use the breadth-first search algorithm for traversing the graph for each query.

Let’s consider any two nodes in the graph ‘A’ and ‘B’, then the path from ‘A’ to ‘B’ will denote the fraction A/B, and it’s value will be equal to multiplication of the weights of all edges on the path from ‘A’ to ‘B’.

Let’s consider the following path from ‘A’ to ‘B’ (A -> X -> Y -> Z); we know that each directed of the form P -> Q represents a fraction P/Q; hence the value of this path will be (A / X) * (X / Y) * (Y / Z) = A / Z.

The steps are as follows :

1. Iterate through the ‘EQUATIONS’ array; let’s say we are currently at index ‘i’.
   • Insert an edge from the numerator variable to the denominator variable with weight equal to ‘VALUES[i]'.
   • Also, insert an edge from the denominator variable to the numerator variable with a weight equal to 1 / ‘VALUES[i]’.
2. Iterate through the queries; let’s say the numerator and denominator for the current query are ‘NUM' and ‘DEN’.
   • Traverse the graph to find a path from ‘NUM' and ‘DEN’ using the Breadth-First Search Algorithm.
   • If there is no such path, then the value cannot be determined. Hence the result for this query will be -1.
   • Otherwise, the answer for this query will be the product of all values on the path from ‘NUM' to ‘DEN’.

In this approach, like the previous approach, we create a directed weighted graph for any equation X/Y = C, Y is the parent of X, and the distance from Y to X is C. Each time we move a node up in the graph to get the result of the equation we multiply the path length

For example:

Given X / Y=C and Y/ Z =B, The graph would be like Z - > Y -> X. To get the result of X / Z, we start with 1 and multiply it by the path weight of Y -> X and Z -> Y

• Then for every equation given, we union the nodes, update each node’s root and add the distance of each node to its root.
• For each query, if the A/B if the roots of A and B are equal, then it’s possible to find the equation A/B  that is the distance(A)/distance(B); otherwise, it is not possible -1 is the answer.

Each time we find a parent of a node we update its distance also, distance(node) = distance(node)*distance(parent)

We create a function getRoot(roots, distances, node) to find a node’s distance from its root. Here the roots are the map of all nodes and their roots. The distances is the map of distances or factors of each node from its root. The node is the current node. 

Algorithm:

• In the getRoot(roots, distances, node)
  • If the node is not is roots
    • Set roots[node] as node 
    • Set distances[node] as 1
    • Return node
  • If roots[node] is equal to the node
    • Return node
  • Set parent as roots[node]
  • Set parentRoot as getRoot(roots, distances, parent)
  • Set roots[node] as parentRoot
  • Set distances[node] as distance[node] * distance[parent]
  • Return parentRoot

• Initialise two empty hashmaps distances and roots
• Iterate i from 0 to size of equations -1
  • Set equation as equations[i]
  • Set root1 as getRoot(roots, distances, equation[0])
  • Set root2 as getRoot(roots, distances, equation[1])
  • Set roots[root1] as root2
  • Set distances[root1] as distances[equation[1]] * values[i] / distances[eqaution[0]]
• Initialise an empty array results
• Iterate query through queries
  • If query[0] is not roots or query[1] is not in roots, then
    • Insert -1 in results
    • Continue the loop
    • Set root1 as getRoot(roots, distances, query[0])
  • Set root2 as getRoot(roots, distances, query[1])
  • If root1 is not equal to root2
    • Insert -1 into results
    • Continue the loop
  • Insert distances[query[0]] / distances[query[1]] in the results array
• Finally return results