Can somebody tell what is wrong in my code

help
, ,
1

Problem link- - LeetCode

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;
    }
};
2

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
3

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

4

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!

5

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

Accepted

6

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

7

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
8

thanks