题目描述

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<double>& values, vector<pair<string, string>> queries, where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

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.

题意：给出方程式 A / B = k, 其中A 和 B 均为代表字符串的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回-1.0。

算法1

(BFS)

题解1：建立有向图 + BFS。我们可以按照给定的关系去建立一个有向图，如果当前a / b = 2.0，那么w[a][b] = 2.0,w[b][a] = 0.5，询问假设为x / y，如果我们能从x出发通过BFS到达y，那么路径上的乘积就是我们需要的答案。如果待查询的字符串没有遇到过或者无法遍历到，就返回-1。

C++ 代码

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int n = equations.size(),idx = 0;
        unordered_map<string,int> hash;
        vector<string> node;
        for(int i = 0 ; i < n ; i ++)
        {
            string a = equations[i][0],b = equations[i][1];
            if(hash.find(a) == hash.end())
                node.push_back(a),hash[a] = idx ++;
            if(hash.find(b) == hash.end())
                node.push_back(b),hash[b] = idx ++;
        }
        int m = node.size();
        vector<vector<double>> w(m,vector<double>(m,0.0));
        for(int i = 0 ; i < n ; i ++)
        {
            int from = hash[equations[i][0]],to = hash[equations[i][1]];
            w[from][to] = values[i];
            if(values[i] != 0) w[to][from] = (1.0 / values[i]);
        }
        vector<double> res;
        for(auto query:queries)
        {
            if(hash.find(query[0]) == hash.end() || hash.find(query[1]) == hash.end())
                {res.push_back(-1.0);continue;}
            int from = hash[query[0]],to = hash[query[1]];
            if(from == to) {res.push_back(1.0);continue;}
            double ans = -1.0;
            queue<pair<int,double>> q;
            q.push(make_pair(from,1.0));
            vector<int> vis(m,0);
            vis[from] = 1;
            bool flag ;
            while(!q.empty())
            {
                flag = false;
                auto t = q.front();
                q.pop();
                for(int i = 0 ; i < m ; i ++)
                {
                    if(w[t.first][i] > 0 && vis[i] == 0)
                    {
                        if(i == to)
                        {
                            ans = t.second * w[t.first][i];
                            flag = true;
                            break;
                        }  
                        vis[i] = 1;
                        q.push(make_pair(i,t.second * w[t.first][i]));
                    }
                }
                if(flag)
                {
                    res.push_back(ans);
                    break;
                }
            }   
            if(flag == false)
                res.push_back(-1.0);
        }
        return res;
    }
};

算法2

(带权值并查集)

题解2：带权值的并查集。我们使用fa维护每个字符串的根字符串，d维护每个字符串的根字符串是当前字符串的多少倍。带权值的并查集与朴素并查集的区别在于：首先这个距离是有向的距离，比如根节点比当前节点大多少，而不能是两个相差多少。

在查找并查集的时候：

• 如果当前节点不是根节点，那么在查找其根节点的过程中，首先要记录旧的根节点是多少，获得新的根节点后，我们要更新当前节点到新的根节点的距离。这个新距离等于当前节点到旧的根节点的距离加上（广义的加，也可以是乘法，异或等等）旧的根节点到新的根节点的距离。

• 在合并并查集的时候，(x,y,dist)代表x和y的距离为dist，我们首先求出两个节点的根节点fx,fy。同时让fy指向fx，这时候我们需要更新的仅仅是d[fy]，fy的子节点的距离更新会在getfa(p)的时候更新。

以这题为例这时候我们有如下等式：fx / x = d[x]，fy / y = d[y]，x / y = dist

合并后得到d[fy] = fx / fy = dist * d[x] / d[y]

所以本题的思路就是：

• 先遍历一遍已知等式建立带权值的并查集。
• 对于每个询问，如果有变量不在并查集中或者两个变量不在一个连通分量中，返回-1。
• 否则，计算出两个变量到根节点的距离，得到答案

C++ 代码

class Solution {
public:
    unordered_map<string,string> fa;
    unordered_map<string,double> d;
    string getfa(string x)
    {
        if(x != fa[x]) 
        {
            string p = fa[x];
            fa[x] = getfa(fa[x]);
            d[x] = d[x] * d[p];
        }
        return fa[x];
    }
    void uni(string x,string y,double val)
    {
        string fx = getfa(x),fy = getfa(y);
        if(fx != fy)
        {
            fa[fy]  = fx;
            d[fy] = val * d[x] / d[y]; 
        }
    }
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int idx = 0;
        for(auto e:equations)
        {
            if(fa.find(e[0]) == fa.end()) 
            {
                fa[e[0]] = e[0];
                d[e[0]] = 1.0;
            }
            if(fa.find(e[1]) == fa.end()) 
            {
                fa[e[1]] = e[1];
                d[e[1]] = 1.0;
            }
            uni(e[0],e[1],values[idx ++]);
        }
        vector<double> res;
        for(auto query:queries)
        {
            if(fa.find(query[0]) == fa.end() || fa.find(query[1]) == fa.end() || getfa(query[0]) != getfa(query[1]))
            {
                res.push_back(-1);
                continue;
            }
            if(query[0] == query[1])
            {
                res.push_back(1.0);
                continue;
            }
            double f1 = d[query[0]],f2 = d[query[1]];
            res.push_back(f2 / f1);
        }
        return res;
    }
};