/**
1. 根据已给等式求解新等式的值, 主要是怎么描述已有变量的相对关系, 因为已给等式都是二元的, 所以可以建图来求
1.1  根据除法建边: a/b =2.0  :   a -> b (rank:2.0) , b->a (rank:0.5)
1.2  根据新等式查值:  a/c = ?  -> 累乘 a .... c 路径上所有边的值
1.3  变量不存在返回-1.0

2. 建图后深搜: (5/11后OOM了, 可能是路径太深)
2.1 搜索顺序: 累加结果, 达到后跳出
2.2 搜索状态: cur, target   |   graph, res
2.3 剪枝:   每次获得结果后缓存到图内

3. 建图后宽搜:
3.1 搜索顺序: 使用map 记录start点到当前点的路径值并作去重, 一直搜索到target位置, 输出map[target]


4. 带权并查集: 
4.1 因为结果是求两点间的路径值, 如果知道a->b 和 a->c 的值, 就能求出 b->c 的值, 所以可以用并查集压缩所有边, 并记录当前节点与父节点的关系
4.2 find 操作: 路径压缩的同时更新路径权值
    X的父节点 -> x的父节点的父节点
    rank[x] -> rank[x] * rank[fa]

4.3 union 操作: 合并集合时更新子节点的路径权值
    如果 x = v * y , 那把y 集合合并到 x 上更新 fy
            fx    rank[x] * x    rank[x]
rank[fy] =  __ =  ___________ = ________  * v
            fy    rank[y] * y    rank[y]
*/


class Solution {

    class Edge{
        String y;
        boolean isMul;
        double rank;
        public Edge(String y, double rank, boolean isMul){
            this.y = y;
            this.rank = rank;
            this.isMul = isMul;
        }
    }

    class UnionFindSet{
        Map<String, String> pre;
        Map<String, Double> rank;
        public UnionFindSet(int n){
            rank = new HashMap<>();
            pre = new HashMap<>();
        }

        public String init(String x){
            String fa = pre.get(x);
            if (fa == null)  pre.put(x, x);
            if (rank.get(x) == null) rank.put(x, 1.0);
            return pre.get(x);
        }

        public String find(String x){
            String fa = init(x);
            if (!fa.equals(x)){
                pre.put(x, find(fa));
                rank.put(x, rank.get(fa) * rank.get(x));
            }
            return pre.get(x);
        }

        public boolean union(String x, String y, double v){
            String fx = find(x);
            String fy = find(y);
            if (fx == fy) return false;
            pre.put(fy, fx);
            rank.put(fy, v * rank.get(x) / rank.get(y));
            return true;
        }
    }

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        return quiz(equations, values, queries);
        // return search(equations, values, queries);
    }

    double[] quiz(List<List<String>> equations, double[] values, List<List<String>> queries) {
        UnionFindSet ufs = new UnionFindSet(26);
        for (int i = 0 ; i < equations.size(); i++){
            List<String> equation = equations.get(i);
            String x = equation.get(0);
            String y = equation.get(1);
            ufs.union(x, y, values[i]);
        }

        double[] result = new double[queries.size()];
        for (int i = 0 ; i < queries.size(); i ++){
            List<String> query = queries.get(i);
            String x = query.get(0);
            String y = query.get(1);
            if (ufs.rank.get(x) == null || ufs.rank.get(y) == null) {
                result[i] = -1.0;
            } else {
                String fx = ufs.find(x);
                String fy = ufs.find(y);
                result[i] = fx != fy ? -1.0 : ufs.rank.get(y) / ufs.rank.get(x);
            }
        }
        return result;
    }

    double[] search(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Set<Edge>> graph = build(equations, values);
        int n = queries.size();
        double[] result = new double[n];
        for (int i = 0; i < n ; i ++){
            result[i] = suggest(queries.get(i), graph);
        }
        return result;
    }

    double suggest(List<String> query, Map<String, Set<Edge>> graph){
        String x = query.get(0);
        String y = query.get(1);
        if (graph.get(x) == null || graph.get(y) == null) return -1.0;
        if (x.equals(y)) return 1.0;
        return bfs(x, y, graph);

        // double[] res = {1.0, 1.0};
        // boolean r = dfs(x, y, res, graph);
        // graph.get(x).add(new Edge(y, res[0], true));
        // graph.get(y).add(new Edge(x, res[0], false));
        // return r ? res[0]/res[1] : -1.0;
    }

    double bfs(String x, String y, Map<String, Set<Edge>> graph){
        Queue<String> queue = new LinkedList<>();
        Map<String, Double> values = new HashMap<>();        
        queue.offer(x);
        values.put(x, 1.0);

        while (!queue.isEmpty()){
            String top = queue.poll();
            double value = values.get(top);
            Set<Edge> edges = graph.get(top);
            for (Edge e : edges){
                if (values.get(e.y) != null) continue;
                values.put(e.y, e.isMul ? value * e.rank : value / e.rank);
                queue.offer(e.y);
            }
        }
        Double res = values.get(y);
        return res == null ? -1.0 : res;
    }

    boolean dfs(String x, String y, double[] res, Map<String, Set<Edge>> graph){
        if (x.equals(y)) return true;
        Set<Edge> edges = graph.get(x); 
        for(Edge e : edges){
            double[] old = {res[0], res[1]};

            if (e.isMul) res[0] *= e.rank;
            else res[1]  *= e.rank;

            boolean r = dfs(e.y, y, res, graph);
            if (r) return true;

            res[0] = old[0];
            res[1] = old[1];
        }
        return false;
    }

    Map<String, Set<Edge>> build(List<List<String>> equations, double[] values){
        int n = equations.size();
        Map<String, Set<Edge>> graph = new HashMap<>();
        for (int i = 0 ; i < n ; i ++){
            List<String> equation = equations.get(i);
            String x = equation.get(0);
            String y = equation.get(1);
            double rank = values[i];

            if (graph.get(x) == null) graph.put(x, new HashSet<Edge>());
            graph.get(x).add(new Edge(y, rank, true));

            if (graph.get(y) == null) graph.put(y, new HashSet<Edge>());
            graph.get(y).add(new Edge(x, rank, false));
        }
        return graph;
    }
}