> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/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/algorithm-practice/leetcode/graph/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"] ].
```

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

## 2. Implementation

**(1) 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.length == 0 || equations[0].length == 0) {
            return res;
        }

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

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

            Edge edge1 = new Edge(vertex2, values[i]);
            Edge edge2 = new Edge(vertex1, 1 / values[i]);

            if (adjList.containsKey(vertex1)) {
                adjList.get(vertex1).add(edge1);
            }
            else {
                List<Edge> edges = new ArrayList<>();
                edges.add(edge1);
                adjList.put(vertex1, edges);
            }

            if (adjList.containsKey(vertex2)) {
                adjList.get(vertex2).add(edge2);
            }
            else {
                List<Edge> edges = new ArrayList<>();
                edges.add(edge2);
                adjList.put(vertex2, edges);
            }
        }

        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, adjList, 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>> adjList, double[] res) {
        if (!adjList.containsKey(start) || !adjList.containsKey(end)) {
            res[index] = -1.0;
            return;
        }

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

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


        visited.add(start);
        List<Edge> edges = adjList.get(start);

        for (Edge edge : edges) {
            dfs(edge.val, end, value * edge.weight, index, visited, adjList, res);
        }
    }
}
```

**(2) BFS**&#x20;

```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.length == 0 || equations[0].length == 0) {
            return res;
        }

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

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

            Edge edge1 = new Edge(vertex2, values[i]);
            Edge edge2 = new Edge(vertex1, 1 / values[i]);

            if (adjList.containsKey(vertex1)) {
                adjList.get(vertex1).add(edge1);
            }
            else {
                List<Edge> edges = new ArrayList<>();
                edges.add(edge1);
                adjList.put(vertex1, edges);
            }

            if (adjList.containsKey(vertex2)) {
                adjList.get(vertex2).add(edge2);
            }
            else {
                List<Edge> edges = new ArrayList<>();
                edges.add(edge2);
                adjList.put(vertex2, edges);
            }
        }

        for (int i = 0; i < queries.length; i++) {
            String start = queries[i][0];
            String end = queries[i][1];
            Set<String> visited = new HashSet<>();
            bfs(start, end, i, visited, adjList, res);
            if (res[i] == 0 && !start.equals(end)) {
                res[i] = -1.0;
            }
        }
        return res;
    }

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

        Queue<String> queue = new LinkedList<>();
        Queue<Double> values = new LinkedList<>();

        queue.add(start);
        values.add(1.0);

        while (!queue.isEmpty()) {
            String curVertex = queue.remove();
            double curValue = values.remove();

            if (!adjList.containsKey(curVertex)) {
                res[index] = -1.0;
                return;
            }

            if (curVertex.equals(end)) {
                res[index] = curValue;
                return;
            }

            if (visited.contains(curVertex)) {
                continue;
            }

            visited.add(curVertex);

            for (Edge edge : adjList.get(curVertex)) {
                String nextVertex = edge.val;
                queue.add(nextVertex);
                double nextValue = curValue * edge.weight;
                values.add(nextValue);
            }
        }
    }
}
```

## 3. Time & Space Complexity

DFS:

BFS: