> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/union-find/399-evaluate-division.md).

# 399 Evaluate Division

## 399. [Evaluate Division](https://leetcode.com/problems/evaluate-division/description/)

## **1. Question**

Equations are given in the format`A / B = k`, where`A`and`B`are variables represented as strings, and`k`is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return`-1.0`.

**Example:**\
Given`a / b = 2.0, b / c = 3.0.`\
queries are:`a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .`\
return`[6.0, 0.5, -1.0, 1.0, -1.0 ].`

The input is:`vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries`, where`equations.size() == values.size()`, and the values are positive. This represents the equations. Return`vector<double>`.

According to the example above:

```
equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
```

## 2. Implementation

**(1) Union Find**

思路: 用union find的思路主要是将 a/b公式中的分母(在这里是b)作为分子的parent, 如果我们知道a/b, 和b/c的值，则要查询a/c时，我们只需要知道a和c在union find里的root, 如果他们有共同的root, 则有解，否则无解。我觉得union find的解法，**关键是如何设置node的parent**，通过代码可以发现，我们将node b设为node a的parent当:

* a和b都不在图中，而b是equation中的分母，a是对应的分子
* b已经出现在图中，而a不在
* 如果a和b都在图中，找出a和b对应的root，将a的root的parent设为b的root的parent

```java
class Solution {
    class Node {
        String parent;
        double ratio;

        public Node(String parent, double ratio) {
            this.parent = parent;
            this.ratio = ratio;
        }
    }

    class UnionFind {
        Map<String, Node> nodes = new HashMap();

        public Node find(String s) {
            if (!nodes.containsKey(s)) {
                return null;
            }

            Node curNode = nodes.get(s);

            if (!curNode.parent.equals(s)) {
                Node parentNode = find(curNode.parent);
                curNode.parent = parentNode.parent;
                curNode.ratio *= parentNode.ratio;
            }
            return curNode;
        }

        public void union(String a, String b, double ratio) {
            boolean hasA = nodes.containsKey(a);
            boolean hasB = nodes.containsKey(b);

            if (!hasA && !hasB) {
                nodes.put(a, new Node(b, ratio));
                nodes.put(b, new Node(b, 1.0));
            }
            else if (!hasA) {
                nodes.put(a, new Node(b, ratio));
            }
            else if (!hasB) {
                nodes.put(b, new Node(a, 1.0 / ratio));
            }
            else {
                Node rootA = find(a);
                Node rootB = find(b);
                rootA.parent = rootB.parent;
                rootA.ratio = ratio / rootA.ratio * rootB.ratio;
            }
        }
    }
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        UnionFind uf = new UnionFind();

        for (int i = 0; i < equations.length; i++) {
            uf.union(equations[i][0], equations[i][1], values[i]);
        }

        double[] res = new double[queries.length];

        for (int i = 0; i < queries.length; i++) {
            Node rootX = uf.find(queries[i][0]);
            Node rootY = uf.find(queries[i][1]);

            if (rootX == null || rootY == null || !rootX.parent.equals(rootY.parent)) {
                res[i] = -1.0;
            }
            else {
                res[i] = rootX.ratio / rootY.ratio;
            }
        }
        return res;
    }
}
```

**(2) DFS**

```java
class Solution {
    class Edge {
        String val;
        double weight;

        public Edge(String val, double weight) {
            this.val = val;
            this.weight = weight;
        }
    }


    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        double[] res = new double[queries.length];

        if (equations == null || equations.length == 0) {
            return res;
        }

        Map<String, List<Edge>> graph = new HashMap();

        for (int i = 0; i < equations.length; i++) {
            String[] equation = equations[i];
            String vertex1 = equation[0];
            String vertex2 = equation[1];

            graph.putIfAbsent(vertex1, new ArrayList());
            graph.get(vertex1).add(new Edge(vertex2, values[i]));

            graph.putIfAbsent(vertex2, new ArrayList());
            graph.get(vertex2).add(new Edge(vertex1, 1/values[i]));
        }

        for (int i = 0; i < queries.length; i++) {
            String start = queries[i][0];
            String end = queries[i][1];

            Set<String> visited = new HashSet();
            dfs(start, end, 1.0, i, visited, graph, res);

            if (res[i] == 0 && !start.equals(end)) {
                res[i] = -1.0;
            }
        }
        return res;
    }

    public void dfs(String start, String end, double value, int index, Set<String> visited, Map<String, List<Edge>> graph, double[] res) {
        if (!graph.containsKey(start) || !graph.containsKey(end)) {
            res[index] = -1.0;
            return;
        }


        if (start.equals(end)) {
            res[index] = value;
            return;
        }

        if (visited.contains(start)) {
            return;
        }

        visited.add(start);
        for (Edge edge : graph.get(start)) {
            dfs(edge.val, end, value * edge.weight, index, visited, graph, res);
        }
    }
}
```

## 3. Time & Space Complexity

**(1)** **Union Find:** 时间复杂度O(e + q), 创建union find需要O(e)时间, e是equations的长度, 每次query的需要O(1)时间，所以总的query时间是O(q), 两部分加起来是O(e + q), 空间复杂度O(e)， 空间主要是创建Union Find时，用到的map需要node的个数

**(2) DFS:** 时间复杂度(e + q\*e), O(e)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/oj-practices/chapter1/union-find/399-evaluate-division.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.