# [C++ Union Find Solution] O(n) for preprocessing, O(1) for each query

• class Solution {
public:
void merge (map<string, int> &groups, map<string, double> &weights, string a, string b, double value, int &index) {
if (groups.find(a) == groups.end() && groups.find(b) == groups.end()) {
groups[a] = index;
groups[b] = index;
++index;

weights[a] = value;
weights[b] = 1.0;
} else if (groups.find(a) != groups.end() && groups.find(b) == groups.end()) {
groups[b] = groups[a];
weights[b] = weights[a] / (value == 0.0 ? (1.0 / INT_MAX) : value);
} else if (groups.find(a) == groups.end() && groups.find(b) != groups.end()) {
groups[a] = groups[b];
weights[a] = weights[b] * value;
} else {
if (groups[a] != groups[b]) {
int agroup = groups[a], bgroup = groups[b];
double ratio = weights[a] / ((weights[b] == 0.0 ? (1.0 / INT_MAX) : weights[b]) * value);

for (auto mit = groups.begin(); mit != groups.end(); ++mit) {
if (mit->second == bgroup) {
groups[mit->first] = agroup;
weights[mit->first] = ratio * weights[mit->first];
}
}
}
}
}

vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values,
vector<pair<string, string>> queries) {
vector<double> res;
int index = 0;
map<string, int> groups;
map<string, double> weights;

for (int i = 0; i < equations.size(); ++i)
merge (groups, weights, equations[i].first, equations[i].second, values[i], index);
for (pair<string, string> pit : queries) {
string a = pit.first, b = pit.second;
if (groups.find(a) == groups.end() || groups.find(b) == groups.end() || groups[a] != groups[b])
res.push_back(-1.0);
else res.push_back(weights[a] / weights[b]);
}
return res;
}
};

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