M399. Evaluate Division description:
  You are given an array of variable pairs equations and an array of real numbers values, where $equations[i] = [A_i, B_i]$ and $values[i]$ represent the equation $A_i / B_i = values[i]$. Each $A_i$ or $B_i$ is a string that represents a single variable.
  You are also given some queries, where $queries[j] = [C_j, D_j]$ represents the jth query where you must find the answer for $C_j / D_j = ?$.
  Return the answers to all queries. If a single answer cannot be determined, return $-1.0$.

Constraints:
  $1 <= equations.length <= 20$
  $equations[i].length == 2$
  $1 <= A_i.length, B_i.length <= 5$
  $values.length == equations.length$
  $0.0 < values[i] <= 20.0$
  $1 <= queries.length <= 20$
  $queries[i].length == 2$
  $1 <= C_j.length, D_j.length <= 5$
  $A_i, B_i, C_j, D_j$ consist of lower case English letters and digits.

There are quite a few graph related problems recently, this is an interesting one. The first intuition would be finding the shortest path, or just any path, and then multiplying the numbers. But come to think about it, it would be a waste of resources if we find the path for each query. Instead, we can store the previous results for future use. Actually, there’s an even easier approach: After we build the graph, we can simply assign a value for each variable based on the equations. Here is an example:

class Solution {
    int parent[40];
    int size[40];
    int find_set(int v) {
        if (v == parent[v]) return v;
        return parent[v] = find_set(parent[v]);
    }
    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (size[a] < size[b])
                swap(a, b);
            parent[b] = a;
            size[a] += size[b];
        }
    }
    unordered_map<string,int> mp;
    double value[40];
    int q[40];
    double tab[40][40];
    int adj[40][40];
    int adjLen[40];
    void init(const vector<vector<string>>& equations,const vector<double>& values){
        memset(size,1,sizeof(size));
        //memset(tab,0.0,sizeof(tab));
        memset(adj,-1,sizeof(adj));
        memset(adjLen,0,sizeof(adjLen));
        memset(value,0.0,sizeof(value));
        mp.clear();
        int cnt=0;
        for(int i=0;i<equations.size();++i){
            auto it0=mp.find(equations[i][0]),it1=mp.find(equations[i][1]);
            int n0,n1;
            if(it0==mp.end()){
                if(it1==mp.end()){
                    it1=mp.insert({equations[i][1],cnt++}).first;
                    n1=it1->second;
                    parent[n1]=n1;
                }
                it0=mp.insert({equations[i][0],cnt++}).first;
                n0=it0->second;
                parent[n0]=n1;
            }
            else if(it1==mp.end()){
                n0=it0->second;
                it1=mp.insert({equations[i][1],cnt++}).first;
                n1=it1->second;
                parent[n1]=parent[n0];
            }
            else{
                n0=it0->second;
                n1=it1->second;
                union_sets(n0,n1);
            }
            adj[n0][adjLen[n0]++]=n1;
            adj[n1][adjLen[n1]++]=n0;
            tab[n0][n1]=values[i];
            tab[n1][n0]=1/values[i];
        }
        for(int i=0;i<cnt;++i){
            if(parent[i]!=i) continue;
            value[i]=1;
            q[0]=i;
            int l=0,r=1;
            while(l<r){
                int curr=q[l++];
                for(int j=0;j<adjLen[curr];++j){
                    int nei=adj[curr][j];
                    double& v=value[nei];
                    if(v==0.0){
                        v=value[curr]/tab[curr][nei];
                        q[r++]=nei;
                    }
                }
            }
        }
        // for(auto it=mp.begin();it!=mp.end();++it){
        //     cout<<it->first<<"("<<parent[it->second]<<")"<<"=";
        //     cout<<value[it->second]<<",";
        // }
        // cout<<endl;
    }
public:
    vector<double> calcEquation(const vector<vector<string>>& equations, const vector<double>& values, const vector<vector<string>>& queries) {
        init(equations,values);
        const int qsz=queries.size();
        vector<double> res(qsz);
        for(int i=0;i<qsz;++i){
            if(mp.find(queries[i][0])==mp.end()||mp.find(queries[i][1])==mp.end()){res[i]=-1;continue;}
            auto v0=mp[queries[i][0]],v1=mp[queries[i][1]];
            if(v0==v1){res[i]=1;continue;}
            if(find_set(v0)!=find_set(v1)){res[i]=-1;continue;}
            res[i]=value[v0]/value[v1];
        }
        return res;
    }
};

First, we initialize the adjacency list and the table of quotients. We read the equations and use disjoint set union algorithm to find the connected components. After that, we find the root of each component and assign $1$ to its value, then update the values of all the other variables in the component based on the table with bfs. Then we process the queries, which we simply check if the variables are both known and if they are in the same component, if so we divide their values to get the result.

It’s hard to tell how the performance is because the test cases are quite small, all the submissions are 0ms. But I think this algorithm is a good balance between code complexity and efficiency. There are a few places that we can improve, though. First, if there are few queries, we don’t need to assign a value to all the variables. Second, imagine a different problem: The input format is {“string1”,”string2”,”number”}, where “number==0.0” means it’s a query at the current input, otherwise it means it gives the value of “string1” divided by “string2”. The algorithm above would be very inefficient in this case. Can we modify the algorithm, so that it updates the values when a new input is given?

It turns out that we can modify the disjoint sets union algorithm to achieve this goal:

class Solution {
    pair<int,double> parent_value[40];
    int size[40];
    pair<int,double> find_set(int v) {
        auto& pv=parent_value[v];
        if (v == pv.first) return pv;
        auto rv=find_set(pv.first);
        return {pv.first=rv.first,pv.second*=rv.second};
    }
    void union_sets(int a, int b,double a_b) {
        auto pa = find_set(a);
        auto pb = find_set(b);
        if (pa.first != pb.first) {
            if (size[pa.first] < size[pb.first]){
                swap(pa, pb);
                a_b=1/a_b;
            }
            parent_value[pb.first]={pa.first,pa.second/pb.second/a_b};
            size[pa.first] += size[pb.first];
        }
    }
    unordered_map<string,int> mp;
    void init(const vector<vector<string>>& equations,const vector<double>& values){
        memset(size,1,sizeof(size));
        memset(parent_value,0.0,sizeof(parent_value));
        mp.clear();
        int cnt=0;
        for(int i=0;i<equations.size();++i){
            auto it0=mp.find(equations[i][0]),it1=mp.find(equations[i][1]);
            int n0,n1;
            if(it0==mp.end()){
                if(it1==mp.end()){
                    it1=mp.insert({equations[i][1],cnt++}).first;
                    n1=it1->second;
                    parent_value[n1]={n1,1};
                }
                it0=mp.insert({equations[i][0],cnt++}).first;
                n0=it0->second;
                parent_value[n0]={n1,parent_value[n1].second*values[i]};
            }
            else if(it1==mp.end()){
                n0=it0->second;
                it1=mp.insert({equations[i][1],cnt++}).first;
                n1=it1->second;
                parent_value[n1]={parent_value[n0].first,parent_value[n0].second/values[i]};
            }
            else{
                n0=it0->second;
                n1=it1->second;
                union_sets(n0,n1,values[i]);
            }
        }
    }
public:
    vector<double> calcEquation(const vector<vector<string>>& equations, const vector<double>& values, const vector<vector<string>>& queries) {
        init(equations,values);
        const int qsz=queries.size();
        vector<double> res(qsz);
        for(int i=0;i<qsz;++i){
            if(mp.find(queries[i][0])==mp.end()||mp.find(queries[i][1])==mp.end()){res[i]=-1;continue;}
            auto v0=mp[queries[i][0]],v1=mp[queries[i][1]];
            if(v0==v1){res[i]=1;continue;}
            if(find_set(v0).first!=find_set(v1).first){res[i]=-1;continue;}
            res[i]=parent_value[v0].second/parent_value[v1].second;
        }
        return res;
    }
};

This way, we can update the value upon each query.