Satisfiability of Equality Equations

Given an arrayequations of strings that represent relationships between variables, each stringequations[i] has length4and takes one of two different forms:"a==b"or"a!=b". Here,aandbare lowercase letters (not necessarily different) that represent one-letter variable names.

Returntrue if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

Example

Example 1:

Input: 
["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: 
["b==a","a==b"]
Output: 
true
Explanation: 
We could assign a = 1 and b = 1 to satisfy both equations.

Example 3:

Input: 
["a==b","b==c","a==c"]
Output: 
true

Example 4:

Input: 
["a==b","b!=c","c==a"]
Output: 
false

Example 5:

Input: 
["c==c","b==d","x!=z"]
Output: 
true

Note

静态联通性，使用Union-Find

等号全部连接在一起，再单独判断不等号，如果连接：就false了

Code

class Solution {
    class UF {
        int[] father;
        public UF() {
            this.father = new int[26];
            for (int i = 0; i < 26; i++) {
                father[i] = i;
            }
        }

        int find(int x) {
            if (x == father[x]) {
               return x;
            } 

            return father[x] = find(father[x]);
        }

        void union(int a, int b) {
            int rootA = find(a);
            int rootB = find(b);

            if (rootA != rootB) {
                father[rootA] = rootB;
            }
        }
    }
    public boolean equationsPossible(String[] equations) {
        UF uf = new UF();
        for (String elem : equations) {
            int a = elem.charAt(0) - 'a', b = elem.charAt(3) - 'a';
            if (elem.charAt(1) == '=') {
                uf.union(a, b);
            }
        }

        for (String elem : equations) {
            int a = elem.charAt(0) - 'a', b = elem.charAt(3) - 'a';
            if (elem.charAt(1) == '!' && uf.find(a) == uf.find(b)) {
                return false;
            }
        }

        return true;

    }
}