本文共 2342 字，大约阅读时间需要 7 分钟。

??????????????????????????????????????????????????????????????????????????????Union-Find??????????????????

????

????

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
class Solution {
private:
    struct DsjSet {
        unordered_map
      
        graph;
        unordered_map
       
         weight;
        pair
        
          find(string u) { if (graph[u] == u) { return {u, 1.0}; } string orig_u = u; u = graph[u]; auto res = find(u); double product = weight[orig_u] * res.second; graph[orig_u] = res.first; return {res.first, product}; } void addEdge(string u, string v, double k) { if (graph.find(u) == graph.end()) { graph[u] = u; weight[u] = 1.0; } if (graph.find(v) == graph.end()) { graph[v] = v; weight[v] = 1.0; } auto u_root = find(u); auto v_root = find(v); if (u_root.first == v_root.first) { weight[u] *= k / weight[v]; weight[v] *= k / weight[u]; return; } graph[u_root.first] = v_root.first; weight[u_root.first] *= k * weight[u_root.first] / weight[v_root.first]; } double getWeight(string u, string v) { auto u_root = find(u); auto v_root = find(v); if (u_root.first != v_root.first) { return -1.0; } return u_root.second / v_root.second; } }; public: vector
         
           calcEquation(vector
          
           
            > equations, vector
            
              values, vector
             
              
               > queries) { DsjSet graph; int N = equations.size(); for (int i = 0; i < N; ++i) { string u = equations[i].first; string v = equations[i].second; double k = values[i]; graph.addEdge(u, v, k); } vector
               
                 result; for (auto& query : queries) { string u = query.first; string v = query.second; result.push_back(graph.getWeight(u, v)); } return result; } }; int main() { Solution sol; vector
                
                 
                  > equations = { {"a","b"}, {"b","c"} }; vector
                  
                    values = {2.0, 3.0}; vector
                   
                    
                     > queries = { {"a","c"}, {"b","a"}, {"a","e"}, {"a","a"}, {"x","x"} }; auto result = sol.calcEquation(equations, values, queries); for (auto& res : result) { cout << res << " "; } cout << endl; return 0; }
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

????

???????????????????????????????????