LeetCode-in-Net/LeetCodeNet/G0301_0400/S0399_evaluate_division/Solution.cs at main · jscrdev/LeetCode-in-Net · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
namespace LeetCodeNet.G0301_0400.S0399_evaluate_division {

// #Medium #Array #Depth_First_Search #Breadth_First_Search #Graph #Union_Find #Shortest_Path
// #LeetCode_75_Graphs/DFS #Top_Interview_150_Graph_General
// #2025_07_18_Time_3_ms_(66.56%)_Space_47.65_MB_(86.96%)

using System;
using System.Collections.Generic;

public class Solution {
    private Dictionary<string, string> root;
    private Dictionary<string, double> rate;

    public double[] CalcEquation(
            IList<IList<string>> equations, double[] values, IList<IList<string>> queries) {
        root = new Dictionary<string, string>();
        rate = new Dictionary<string, double>();
        int n = equations.Count;
        foreach (var equation in equations) {
            string x = equation[0];
            string y = equation[1];
            root[x] = x;
            root[y] = y;
            rate[x] = 1.0;
            rate[y] = 1.0;
        }
        for (int i = 0; i < n; ++i) {
            string x = equations[i][0];
            string y = equations[i][1];
            union(x, y, values[i]);
        }
        double[] result = new double[queries.Count];
        for (int i = 0; i < queries.Count; ++i) {
            string x = queries[i][0];
            string y = queries[i][1];
            if (!root.ContainsKey(x) || !root.ContainsKey(y)) {
                result[i] = -1;
                continue;
            }
            string rootX = findRoot(x, x, 1.0);
            string rootY = findRoot(y, y, 1.0);
            result[i] = rootX.Equals(rootY) ? rate[x] / rate[y] : -1.0;
        }
        return result;
    }

    private void union(string x, string y, double v) {
        string rootX = findRoot(x, x, 1.0);
        string rootY = findRoot(y, y, 1.0);
        root[rootX] = rootY;
        double r1 = rate[x];
        double r2 = rate[y];
        rate[rootX] = v * r2 / r1;
    }

    private string findRoot(string originalX, string x, double r) {
        if (root[x].Equals(x)) {
            root[originalX] = x;
            rate[originalX] = r * rate[x];
            return x;
        }
        return findRoot(originalX, root[x], r * rate[x]);
    }
}
}