2307. Check for Contradictions in Equations

You are given a 2D array of strings equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] means that Ai / Bi = values[i].

Determine if there exists a contradiction in the equations. Return true if there is a contradiction, or false otherwise.

Note: When checking if two numbers are equal, check that their absolute difference is less than 10-5.

class Solution {
    bool bfs(string s, unordered_map<string, vector<pair<string, double>>>& adj, unordered_map<string, double> vis) {
        queue<string> q;
        q.push(s);
        vis[s] = 1.0;
        while(!q.empty()) {
            auto u = q.front(); q.pop();
            for(auto& [v, f] : adj[u]) {
                if(vis.count(v)) {
                    if(vis[v] != vis[u] * f)
                        return false;
                } else {
                    vis[v] = f * vis[s];
                    q.push(v);
                }
            }
        }
        return true;
    }
public:
    bool checkContradictions(vector<vector<string>>& equations, vector<double>& values) {
        unordered_map<string, vector<pair<string, double>>> adj;
        unordered_set<string> us;
        unordered_map<string, double> vis;
        int n = values.size();
        for(int i = 0; i < n; i++) {
            string u = equations[i][0], v = equations[i][1];
            double f = values[i];
            adj[u].push_back({v, 1 / f});
            adj[v].push_back({u, f});
            us.insert(u);
            us.insert(v);
        }
        
        for(auto& u : us) {
            if(vis.count(u)) continue;
            if(!bfs(u, adj, vis))
                return true;
        }

        return false;
    }
};