Problem link- Loading...

```
class Solution {
public:
double bfs(string start, string end, unordered_set<string> visited, unordered_map<string,vector<pair<string,double>>> &mp)
{
if(mp.find(start) == mp.end() || mp.find(end) == mp.end()) return -1.0;
if(start == end) return 1.0;
visited.insert(start);
queue<pair<string,int>> q;
q.push({start,1.0});
while(!q.empty())
{
string s=q.front().first;
double temp=q.front().second;
q.pop();
if(s==end)
{
return temp;
}
for(auto it:mp[s])
{
if(!visited.count(it.first))
{
visited.insert(it.first);
q.push({it.first,temp*it.second});
}
}
}
return -1.0;
}
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],values[i]});
mp[equations[i][1]].push_back({equations[i][0],1.0/values[i]});
}
vector<double> ans(queries.size());
for(int i=0;i<queries.size();i++)
{
unordered_set<string> visited;
ans[i]=bfs(queries[i][0],queries[i][1],visited,mp);
}
return ans;
}
};
```

Note that the equations define a weighted directed graph G, where the equation \frac{A}{B} = value can be represented as a pair of weighted edges: B \rightarrow A has weight value and A \rightarrow B has weight \frac{1}{value}, that represent the equations A = value \times B and B = \frac{1}{value} \times A, respectively. The number of nodes in G is equal to the number of distinct names in the equations. To compute the answer for query \frac{C}{D}, either BFS or DFS can be used starting from node D until node C is reached, and the answer to the query is the product of edge weights along the directed path from D to C, which represents that value of C when D = 1.0. The n distinct variable names in the equations array can be encoded using a variable-name map to integer numbers 0,1,\ldots,n-1 to simplify the graph representation and query processing.

You can check the following DFS solution.

Accepted

Check the following update to your map-based solution.

Accepted

The output of your BFS solution for the first query a/c in the given test is 3.0, not 3.75 as expected.

It seems that the **pair<string,double>** data structure used in the BFS solution does not store the floating-point value correctly in the BFS queue for some unknown reason.

1 Like

Thanks

But I had already solved this using DfS but just wanted why pair<string, double> is not working correctly here.

With pleasure. I have no idea what is going on with the **pair<string,double>**. The floating-point value 2.5 pushed to the queue in the second field of the pair is popped from the queue as 2.0! I have not seen such bug before!

The following update to the BFS solution was accepted. The issue is clearly with the queue of **pair<string,double>** object.

Accepted

Another good news for the BFS solution! The **deque** container can be used instead of the **queue** container to store and retrieve the floating-point field correctly.

Accepted

I have just noticed an issue in your BFS implementation.

**queue<pair<string,int>> q**

should have been written as

**queue<pair<string,double>> q**

The push command will surely trim the fractional part of 2.5 to integer value 2 to be stored in the second integer field.

Your code was accepted after changing the second field to **double** as it should be.

1 Like