 # Can somebody tell what is wrong in my code

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]].push_back({equations[i],values[i]});
mp[equations[i]].push_back({equations[i],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],queries[i],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

thanks