Java UnionFind Solution


  • 0
    T

    This is actually a UnionFind question. Please check the code for your reference

    class Solution {
        
        class UnionFind {
            public Map<String, String> father;
            public Map<String, Double> ratio;
            
            public UnionFind() {
                this.father = new HashMap<>();
                this.ratio = new HashMap<>();
            }
            
            public void add(String a) {
                if (!father.containsKey(a)) {
                    father.put(a, a);
                    ratio.put(a, 1.0);
                }
            }
            
            public String find(String a) {
                if (father.get(a).equals(a)) {
                    return a;
                }
                String fa = father.get(a);
                String faOld = new String(fa);
                fa = find(fa);
                father.put(a, fa);
                ratio.put(a, ratio.get(a) * ratio.get(faOld));
                return fa;
            }
            
            public void union(String a, String b, double d) {
                String fa = find(a);
                String fb = find(b);
                father.put(fb, fa);
                ratio.put(fb, d * ratio.get(a) / ratio.get(b));
            }
            
            public double query(String a, String b) {
                if (father.get(a) == null || father.get(b) == null) {
                    return -1.0;
                }
                String fa = find(a);
                String fb = find(b);
                if (!fa.equals(fb)) {
                    return -1.0;
                }
                return ratio.get(b) / ratio.get(a);
            }
        }
        
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            UnionFind uf = new UnionFind();
            for (int i = 0; i < equations.length; i++) {
                String[] equation = equations[i];
                uf.add(equation[0]);
                uf.add(equation[1]);
                uf.union(equation[0], equation[1], values[i]);
            }
            int n = queries.length;
            double[] res = new double[n];
            for (int i = 0; i < n; i++) {
                String[] q = queries[i];
                res[i] = uf.query(q[0], q[1]);
            }
            return res;
        }
    }
    

Log in to reply
 

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