题解 | #牛群之间的体重比# 哈希表 BFS

知识点

BFS 哈希表

思路

我们首先可以知道一些点构成了连通块, 他们之间存在着换算的关系, 也就是说连通块之间可以互相换算, 不连通的点或者根本没有出现的点是不能换算的.

所以我们现在考虑用bfs将每一个连通块的换算标准统一 (即把整个连通块的第一个元素当做换算的代表元素), 在询问的过程中如果双方均出现过而且属于同一个连通块, 则可以有答案, 否则没有确切的答案

如果有答案, 则答案是两者换算为同一元素的值之比 可以时间内计算出来

跑bfs每个点最多入队一次, n为点数, m为询问的次数, 总的时间复杂度为

AC Code (C++)

#include <unordered_map>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param weightRatios string字符串vector<vector<>> 
     * @param ratioValues double浮点型vector 
     * @param questions string字符串vector<vector<>> 
     * @return double浮点型vector
     */
    using psd = pair<string, double>;
    vector<double> calcWeightRatios(vector<vector<string> >& weightRatios, vector<double>& ratioValues, vector<vector<string> >& questions) {
        // 建图
        unordered_map<string, vector<psd>> mp;
        for (int i = 0; i < (int)weightRatios.size(); i ++) {
            string a = weightRatios[i][0], b = weightRatios[i][1];
            double d = ratioValues[i];
            mp[a].push_back({b, d});
            mp[b].push_back({a, 1.0 / d});
        }

        // 把每个连通块计算一下
        unordered_map<string, pair<int, double>> seen;
        int idx = 1;
        for (auto& [k, _] : mp) {
            if (seen.count(k)) continue;
            queue<psd> q;
            q.push({k, 1.0});
            seen[k] = {idx, 1.0};
            while (!q.empty()) {
                auto [ver, sum] = q.front();
                q.pop();
                for (auto [x, d] : mp[ver]) {
                    if (seen.count(x)) continue;
                    seen[x] = {idx, sum * d};
                    q.push({x, sum * d});
                }
            }
            idx += 1;
        }
        vector<double> res;
        for (auto& v : questions) {
            auto a = v[0], b = v[1];
            if (!seen.count(a) or !seen.count(b)) {
                res.push_back(-1.0);
                continue;
            }
            if (seen[a].first != seen[b].first) res.push_back(-1.0);
            else {
                auto ans = seen[b].second / seen[a].second;
                res.push_back(ans);
            }
        }
        return res;
    }
};