Evaluate Division

Given equations of the form a / b = value and queries asking for ratios, return the answers for each query. DSU with weighted edges is the standard extension of union by rank for ratio propagation.

Input Format

equations = variable ratio equations, values = equation results, queries = ratio queries

Output Format

answer for each division query

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

equations = [["aa","bb"],["bb","cc"]]
values = [2,3]
queries = [["aa","cc"],["bb","aa"],["aa","ee"],["aa","aa"],["xx","xx"]]

Output:

[6.0,0.5,-1.0,1.0,-1.0]

Explanation:

a/c = 2 × 3 = 6, b/a = 1/2, unknown variables return -1, and a/a = 1.

Example 2:

Input:

equations = [["xx","yy"]]
values = [4]
queries = [["xx","yy"],["yy","xx"]]

Output:

[4.0,0.25]

Explanation:

The reverse ratio is the reciprocal.

Example 3:

Input:

equations = [["aa","bb"],["cc","dd"]]
values = [1.5,2.5]
queries = [["aa","dd"],["bb","aa"]]

Output:

[-1.0,0.6666666667]

Explanation:

Unconnected components cannot answer cross-component queries.

Loading...
Evaluate Division - Union Find DSA Problem