Can somebody tell what is wrong in my code

Problem link- Loading...

class Solution {
    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;
        queue<pair<string,int>> q;
            string s=q.front().first;
            double temp=q.front().second;
                return temp;
            for(auto it:mp[s])
        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++)
        vector<double> ans(queries.size());
        for(int i=0;i<queries.size();i++)
            unordered_set<string> visited;
        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.


Check the following update to your map-based solution.


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 :grinning:
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.


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.


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