Hey, so today we are going to solve Leetcode - **Evaluate Division**

**Problem Link-** https://leetcode.com/problems/evaluate-division/description/

```
class Solution {
public:
void dfs(unordered_map<string, vector<pair<string, double>>> mp, unordered_map<string, int> &visited, double &ans, double temp, string source, string destination) {
if(visited.count(source)) {
return ;
}
if(source == destination) {
ans = temp;
return;
}
visited[source] = 1;
for(auto x:mp[source]){
dfs(mp, equations, visited, ans, temp*x.second, x.first, destination);
}
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
unordered_map<string, vector<pair<string, double>>> mp;
for(int i =0; i<equations.size(); i++){
mp(equations[i][0]).push_back(equations[i][1], value[i]);
mp(equations[i][1]).push_back(equations[i][0], 1/value[i]);
}
vector<double> finalAns;
for(int i =0; i<queries.size(); i++) {
string source = queries[i][0];
string destination = queries[i][1];
double ans = -1.0;
double temp = 1.0;
unordered_map<string, int> visited;
dfs(mp, visited, ans, temp, source, destination);
finalAns.emplace_back(ans);
}
return finalAns;
}
}
```

Here's an explanation of the code along with an example:

The code defines a class

`Solution`

with a member function`calcEquation`

that takes three parameters:`equations`

,`values`

, and`queries`

. It returns a vector of doubles as the final answer to the queries.Inside the

`calcEquation`

function, an unordered map`mp`

is created. This map is used to store the equations and their corresponding values. It is implemented as`unordered_map<string, vector<pair<string, double>>>`

, where the key is a string representing a variable, and the value is a vector of pairs. Each pair consists of the variable name (string) and its corresponding value (double).A loop is executed to populate the

`mp`

map based on the input equations and values. For each equation, the values are inserted into the map for both variables involved in the equation and their reciprocal values.Another loop is executed to process each query. For each query, a depth-first search (DFS) is performed to find a path from the source variable to the destination variable in the

`mp`

map.The

`dfs`

function is a recursive helper function that performs the DFS. It takes the`mp`

map, equations, visited map, answer variable, current product value, source variable, and destination variable as parameters.In the

`dfs`

function, several checks are performed:If the source variable has been visited before, it is skipped to avoid infinite loops.

If the source and destination variables are the same, the answer variable

`ans`

is updated with the current product value`temp`

, and the function returns.The source variable is marked as visited in the

`visited`

map.

A loop iterates through each adjacent variable of the current source variable using

`mp[source]`

. For each adjacent variable, the`dfs`

function is recursively called, passing the updated`ans`

,`temp`

, and the adjacent variable as the new source.After the DFS completes for a query, the calculated answer

`ans`

is added to the`finalAns`

vector.Finally, the

`finalAns`

vector, containing the answers to all the queries, is returned.

Example: Suppose we have the following equations and values: equations = [["a", "b"], ["b", "c"], ["c", "d"]] values = [2.0, 3.0, 4.0] queries = [["a", "d"], ["b", "d"], ["a", "c"], ["a", "e"]]

The initial `mp`

map will be: mp = { "a": [["b", 2.0]], "b": [["a", 0.5], ["c", 3.0]], "c": [["b", 0.333], ["d", 4.0]], "d": [["c", 0.25]] }

For each query, the code performs a DFS to find the path and calculate the answer.

Query ["a", "d"]:

DFS starts from "a" and goes through "b" and "c" to reach "d".

The product value is 2.0

*0.333*4.0 = 2.664.The answer for this query is 2.664.

Query ["b", "d"] (continued):

The product value is 3.0 * 4.0 = 12.0.

The answer for this query is 12.0.

Query ["a", "c"]:

DFS starts from "a" and goes through "b" to reach "c".

The product value is 2.0 * 3.0 = 6.0.

The answer for this query is 6.0.

Query ["a", "e"]:

Since there is no variable "e" in the equations, the DFS cannot find a path.

The answer for this query is -1.0.

The final answers vector returned by the `calcEquation`

function would be [2.664, 12.0, 6.0, -1.0], representing the answers to the corresponding queries.

Overall, the code implements a depth-first search algorithm to traverse the equations and find the values needed to calculate the answers to the queries. It utilizes an adjacency list representation using an unordered map to store the equations and their values efficiently.

More on the DFS function here:

The `dfs`

function is a recursive function that performs depth-first search on the graph to find the answer to a specific query.

`mp`

is the adjacency list representation of the graph, where each variable is mapped to a vector of pairs representing the neighboring variables and their corresponding edge weights.`visited`

is a map to keep track of visited nodes to avoid visiting the same node multiple times.`ans`

is the reference to the variable that stores the answer for the current query.`temp`

is the current product of edge weights along the path from the source to the current node.`source`

is the current node being visited.`destination`

is the target node we want to reach.

Here's a step-by-step breakdown of how the `dfs`

function works:

If the

`source`

node has already been visited (found in the`visited`

map), it means we have already explored this node, so we return from the current recursive call.If the

`source`

node is the same as the`destination`

node, it means we have reached the target, and we update the`ans`

variable with the current product`temp`

. We then return from the current recursive call.Mark the

`source`

node as visited by adding it to the`visited`

map.Iterate over each neighbor

`x`

of the`source`

node in the adjacency list`mp[source]`

.Recursively call the

`dfs`

function on each neighbor`x`

, passing updated values of`mp`

,`visited`

,`ans`

,`temp * x.second`

, and`x.first`

as arguments. The`temp * x.second`

represents the updated product of edge weights, and`x.first`

represents the next node to visit.Once all recursive calls return, we continue with the next neighbor or return to the previous recursive call.

The `dfs`

function essentially explores the graph using depth-first search, multiplying the edge weights along the path and updating the answer (`ans`

) when the destination is reached. The `visited`

map ensures that we don't revisit the same node, preventing infinite loops in cyclic graphs.