You are given an array of strings equations that represent relationships between variables where each string equations[i] is of length 4 and takes one of two different forms: "xi==yi" or "xi!=yi".Here, xi and yi are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise.

&nbsp;
Example 1:

Input: equations = ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.
There is no way to assign the variables to satisfy both equations.


Example 2:

Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.


&nbsp;
Constraints:


	1 &lt;= equations.length &lt;= 500
	equations[i].length == 4
	equations[i][0] is a lowercase letter.
	equations[i][1] is either '=' or '!'.
	equations[i][2] is '='.
	equations[i][3] is a lowercase letter.


class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        from collections import defaultdict
        g = defaultdict(list)
        for e in equations:
            if e[1] == '=':
                x = e[0]
                y = e[3]
                g[x].append(y)
                g[y].append(x)
        
        # marked the connected components as 0,1,2,...,25
        ccs = defaultdict(lambda: -1) # -1 means unmarked or unseen

        def dfs(node, cc):
            if node not in ccs:
                ccs[node] = cc
                for neighbour in g[node]:
                    dfs(neighbour, cc)
        
        for i in range(26):
            dfs(chr(i+97), i)
        
        for e in equations:
            if e[1] == '!':
                x = e[0]
                y = e[3]
                if ccs[x] == ccs[y]:
                    return False
        return True
class Solution {
    static int par[];

    public static int findPar(int u) {
        return par[u] == u ? u : (par[u] = findPar(par[u]));
    }

    public boolean equationsPossible(String[] equations) {
        par = new int[26];
        for (int i = 0; i < 26; i++) {
            par[i] = i;
        }

        /*First perform all the merging operation*/
        for (String s : equations) {
            int c1 = s.charAt(0) - 'a';
            int c2 = s.charAt(3) - 'a';
            char sign = s.charAt(1);

            int p1 = findPar(c1);
            int p2 = findPar(c2);

            if (sign == '=') {
                if (p1 != p2) {
                    if (p1 < p2) {
                        par[p2] = p1;
                    } else {
                        par[p1] = p2;
                    }
                }
            } 
        }

        /*Now traverse on the whole string and search for any != operation and check if there parents are same*/
        for (String s : equations) {
            int c1 = s.charAt(0) - 'a';
            int c2 = s.charAt(3) - 'a';
            char sign = s.charAt(1);

            int p1 = findPar(c1);
            int p2 = findPar(c2);

            if (sign == '!') {
                if (p1 == p2) {
                    return false;
                }
            }
        }
        return true;
    }
}
class Solution {
public:    
    bool equationsPossible(vector<string>& equations) {
        
        unordered_map<char,set<char>> equalGraph;       //O(26*26)
        unordered_map<char,set<char>> unEqualGraph;     //O(26*26)
        
        //build graph:
        for(auto eq: equations){
            char x = eq[0], y = eq[3];
            if(eq[1] == '='){
                equalGraph[x].insert(y);
                equalGraph[y].insert(x);
            } 
            else{
                unEqualGraph[x].insert(y);
                unEqualGraph[y].insert(x);
            }
        }
        
        //for each node in inequality, check if they are reachable from equality:
        for(auto it: unEqualGraph){
            char node = it.first;
            set<char> nbrs = it.second;         //all nbrs that should be unequal
            if(nbrs.size() == 0) continue;
                        
            unordered_map<char,bool> seen;  
            bool temp = dfs(node, seen, equalGraph, nbrs);
            if(temp) return false;          //if any nbr found in equality, return false
        }
        
        return true;
        //TC, SC: O(N*N) + O(26*26)
    }
    
    
     bool dfs(char curNode, unordered_map<char,bool> &seen, unordered_map<char,set<char>> &equalGraph, set<char> &nbrs){
        
        seen[curNode] = true;
        if(nbrs.find(curNode) != nbrs.end()) return true;
        
        for(auto nextNode: equalGraph[curNode]){
            if(seen.find(nextNode) == seen.end()){
                bool temp = dfs(nextNode, seen, equalGraph, nbrs);
                if(temp) return true;
            }
        }
        
        return false;
    }
    
};
/**
 * @param {string[]} equations
 * @return {boolean}
 */
class UnionSet {
    constructor() {
        this.father = new Array(26).fill(0).map((item, index) => index);
    }
    find(x) {
        return this.father[x] = this.father[x] === x ? x : this.find(this.father[x]);
    }
    merge(a, b) {
        const fa = this.find(a);
        const fb = this.find(b);
        if (fa === fb) return;
        this.father[fb] = fa;
    }
    equal(a, b) {
        return this.find(a) === this.find(b);
    }
}
var equationsPossible = function(equations) {
    const us = new UnionSet();
    const base = 'a'.charCodeAt();
    // merge, when equal
    for(let i = 0; i < equations.length; i++) {
        const item = equations[i];
        if (item[1] === '!') continue;
        const a = item[0].charCodeAt() - base;
        const b = item[3].charCodeAt() - base;
        us.merge(a, b);
    }
    // check, when different
    for(let i = 0; i < equations.length; i++) {
        const item = equations[i];
        if (item[1] === '=') continue;
        const a = item[0].charCodeAt() - base;
        const b = item[3].charCodeAt() - base;
        if (us.equal(a, b)) return false;
    }
    return true;
};
Satisfiability of Equality Equations