# C++, 0ms, graph dfs and union find solution

• First DFS

``````class Solution {
private:
unordered_map<string,unordered_map<string,double>> graph;
unordered_set<string> zeros;

public:
bool dfs(double &res, string cur, string target, unordered_set<string> & visited){
if (graph[cur].count(target)) {
res*=graph[cur][target];
return 1;
}
for (auto &x:graph[cur]){
if (visited.count(x.first)) continue;
res*=x.second;
visited.insert(x.first);
if (dfs(res,x.first,target,visited)) {
visited.erase(x.first);
return 1;
}
res/=x.second;
visited.erase(x.first);
}
return false;
}

double getResult(pair<string,string> &x){
if (graph.count(x.first)==0 || graph.count(x.second)==0) return -1;
if (zeros.count(x.second)) return -1.0;
if (zeros.count(x.first)) return 0;
if (x.first==x.second) return 1.0;
unordered_set<string> visited;
double res=1.0;
if (dfs(res,x.first,x.second,visited))
return res;
else
return -1.0;
}

vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
vector<double> res;
int sz = equations.size();
for (int i=0;i<sz;i++){
if  (values[i]==0) zeros.insert(equations[i].first);
else{
graph[equations[i].first][equations[i].second]=values[i];
graph[equations[i].second][equations[i].first]=1.0/values[i];
}
}
for (auto &x:queries){
res.push_back(getResult(x));
}
return res;
}
};
``````

Then, union find. Obviously, union-find solution is much better for long queries

``````vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {

unordered_map<string,pair<string,double>> graph;
for (int i=0;i<equations.size();i++){
pair<string,double> a,b;
if (graph.count(equations[i].first) && graph.count(equations[i].second)){
a = getParent(graph,equations[i].first);
b = getParent(graph,equations[i].second);
if (a.first==b.first) continue;
else{
graph[a.first].first = b.first;
graph[a.first].second = 1/a.second*values[i]*b.second;
}
}else if(graph.count(equations[i].first)){
a = getParent(graph,equations[i].first);
graph[equations[i].second] = make_pair(a.first,1/values[i]*a.second);
}else if(graph.count(equations[i].second)){
b = getParent(graph,equations[i].second);
graph[equations[i].first] = make_pair(b.first,values[i]*b.second);
}else{
graph[equations[i].first] = make_pair(equations[i].second,values[i]);
graph[equations[i].second] = make_pair(equations[i].second,1);
}
}

vector<double> res;
for (auto &x:queries){
if (!graph.count(x.first) || !graph.count(x.second)){
res.push_back(-1.0);
}else{
pair<string,double> a,b;
a = getParent(graph,x.first);
b = getParent(graph,x.second);
if (a.first!=b.first || b.second==0){
res.push_back(-1.0);
}else{
res.push_back(a.second/b.second);
}
}
}
return res;
}
pair<string,double> getParent(unordered_map<string,pair<string,double>> &graph,string s){
if (graph[s].first!=s){
auto x=getParent(graph,graph[s].first);
graph[s].first=x.first;
graph[s].second*=x.second;
}
return graph[s];
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.