Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations,

vector& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector.

According to the example above:

equations = [ [“a”, “b”], [“b”, “c”] ],

values = [2.0, 3.0],

queries = [ [“a”, “c”], [“b”, “a”], [“a”, “e”], [“a”, “a”], [“x”, “x”] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

思路

dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
struct node{
string num;
double v;
node(string nn,double vv):num(nn),v(vv){}
};
class Solution {
public:
map<string,vector<node> >g;
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
set<string> ss;
for(int i=0;i<equations.size();i++){
pair<string,string> p=equations[i];
g[p.first].push_back(node(p.second,values[i]));
g[p.second].push_back(node(p.first,1/values[i]));
}
vector<double> answer;
set<string> vis;
for(auto b:queries)
{
vis.clear();

if(!g.count(b.first)&&!g.count(b.second)) answer.push_back(-1);
else answer.push_back(dfs(b.first,b.second,vis));

}
return answer;
}
double dfs(string cur,string target,set<string> &vis){
if(cur==target) {
return 1;
}
vis.insert(cur);
for(int i=0;i<g[cur].size();i++){
node t=g[cur][i];
if(!vis.count(t.num)) {
double d=dfs(t.num,target,vis);//!!
if(d>0) return t.v*d;
}
}
return -1;

}

};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct node{
string num;
double v;
node(string nn,double vv):num(nn),v(vv){}
};
class Solution {
public:
map<string,vector<node> >g;
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
set<string> ss;
for(int i=0;i<equations.size();i++){
pair<string,string> p=equations[i];
g[p.first].push_back(node(p.second,values[i]));
g[p.second].push_back(node(p.first,1/values[i]));
ss.insert(p.first);
ss.insert(p.second);
}
vector<double> answer;
set<string> vis;
for(auto b:queries)
{
vis.clear();
double ans=1;
if(!ss.count(b.first)&&!ss.count(b.second)) answer.push_back(-1);
else if(!dfs(b.first,b.second,vis,ans,answer)) answer.push_back(-1);

}
return answer;
}
bool dfs(string cur,string target,set<string> &vis,double &ans,vector<double> &answer){
if(vis.count(cur)) return false;
if(cur==target) {
answer.push_back(ans);
return true;
}
vis.insert(cur);
for(int i=0;i<g[cur].size();i++){
node t=g[cur][i];
if(!vis.count(t.num)) {
double tmp=ans*t.v;
if(dfs(t.num,target,vis,tmp,answer)) return true;
}

}

return false;

}

};