题意：在已知一系列方程的条件下，求另一些方程的值。题目保证方程不会冲突。
思路：将方程归类，有关联的归到一类。这部分用并查集实现。按一定顺序求解方程，这里用了变量名的字典序。
class Solution { struct eq { string nums; string divs; double val; }; public: vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) { vector<eq> e; map<string, double> vals; map<string, string> rmq; rmq[""] = ""; eq tempe; for(int i = 0; i < equations.size(); ++ i) { tempe.nums = equations[i].first; tempe.divs = equations[i].second; tempe.val = values[i]; e.push_back(tempe); vals[equations[i].first] = 0.0; vals[equations[i].second] = 0.0; rmq[equations[i].first] = equations[i].first; rmq[equations[i].second] = equations[i].second; } std::sort(e.begin(), e.end(), [](eq a, eq b){if(a.divs == b.divs) return a.nums < b.nums; else return a.divs < b.divs;}); for(int i = 0; i < e.size(); ++ i) { if(rmq[e[i].nums] == e[i].nums) rmq[e[i].nums] = e[i].divs; else rmq[e[i].divs] = e[i].nums; //cout << e[i].nums << " " << e[i].divs << endl; if(abs(vals[e[i].nums]) > 1e-5) { vals[e[i].divs] = vals[e[i].nums] / e[i].val; } if(abs(vals[e[i].divs]) < 1e-5 ) { vals[e[i].divs] = 1.0; vals[e[i].nums] = vals[e[i].divs] * e[i].val; } else { vals[e[i].nums] = vals[e[i].divs] * e[i].val; } } vector<double> re; for(int i = 0; i < queries.size(); ++ i) { if(abs(vals[queries[i].first]) > 1e-5 && abs(vals[queries[i].second]) > 1e-5) { if(rmqFind(queries[i].first, rmq) == rmqFind(queries[i].second, rmq)) re.push_back(vals[queries[i].first] / vals[queries[i].second]); else re.push_back(-1); } else { re.push_back( -1.0); } } //debug //show(vals); return re; } private: string rmqFind(string s, map<string, string> rmq) { return s == rmq[s]?s:rmqFind(rmq[s], rmq); } //debug void show(map<string, double> m) { std::map<string, double>::iterator it; for(it = m.begin(); it != m.end(); ++ it) { cout << it->first << " " << it->second << endl; } return; } };