All problems

Ratio Chains

Medium · union find

A trading desk deals in n currencies, numbered 0 to n - 1. It has been given some exchange equations, in the list equations. Each entry [a, b, k] says that one unit of currency a is worth exactly k units of currency b, where k is a whole number.

From these equations you can sometimes work out the rate between two currencies that no equation mentions together. If one 0 is worth 3 of 1, and one 1 is worth 2 of 2, then one 0 is worth 6 of 2. You may follow equations in either direction, so one 2 is worth 1/6 of a 0.

The list queries holds questions. Each entry [a, b] asks: how many units of currency b is one unit of currency a worth? Return a list with one answer per query, in the same order.

• If the equations connect a and b, directly or through other currencies, the answer is the rate as a fraction in lowest terms, written as a string "p/q". Whole numbers keep the denominator, so six is "6/1".
• If they do not connect a and b, the answer is the string "-1".
• A currency is always worth exactly one of itself, so a query [a, a] gives "1/1", even if a appears in no equation.

The equations never contradict one another. Many equations may mention the same pair of currencies, and the same equation may be repeated.

Examples

Example 1

Input: n = 4, equations = [[0, 1, 3], [1, 2, 2]], queries = [[0, 2], [2, 0], [0, 3], [3, 3]]

Output: ["6/1", "1/6", "-1", "1/1"]

One 0 is worth 3 of currency 1, which is 3 times 2 = 6 of currency 2, so the first answer is 6/1 and the reverse is 1/6. Currency 3 is not connected to 0, but it is worth one of itself.

Example 2

Input: n = 3, equations = [[1, 0, 2]], queries = [[0, 1], [1, 0]]

Output: ["1/2", "2/1"]

One 1 is worth 2 of currency 0, so one 0 is worth half of a 1.

Example 3

Input: n = 3, equations = [[0, 1, 4], [2, 1, 6]], queries = [[0, 2]]

Output: ["2/3"]

One 0 is worth 4 of currency 1, and one 2 is worth 6 of currency 1, so one 0 is worth 4/6 of a 2, which reduces to 2/3.

Constraints

• 1 <= n <= 10000
• 0 <= len(equations) <= 10000, and each entry is [a, b, k] with 0 <= a, b < n, a != b and 1 <= k <= 100
• 0 <= len(queries) <= 10000, and each entry is [a, b] with 0 <= a, b < n
• For any two currencies connected by the equations, the rate between them in lowest terms is p/q with 1 <= p, q <= 10000.