# 0990. Satisfiability of Equality Equations
###### tags: `Leetcode` `Medium` `Union Find`
Link: https://leetcode.com/problems/satisfiability-of-equality-equations/
## 思路
先把等于的都放在一个group
然后看不等于的 如果两边的字母在同一个group return false
## Code

class Solution {
    int[] fa = new int[26];
    public boolean equationsPossible(String[] equations) {
        for(int i=0; i<26; i++) fa[i] = i;
        for(String eq:equations){
            if(eq.charAt(1)=='=') combine(eq.charAt(0)-'a', eq.charAt(3)-'a');
        }
        for(String eq:equations){
            if(eq.charAt(1)=='!' && find(eq.charAt(0)-'a')==find(eq.charAt(3)-'a')){
                return false;
            } 
        }
        return true;
    }
    private int find(int a){
        if(fa[a]==a) return a;
        return fa[a] = find(fa[a]);
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        fa[a]=b;
    }
}