990. Satisfiability of Equality Equations

Union-Find

Time: O(N)

Space O(1)

class Solution {
    int[] graph;
    public boolean equationsPossible(String[] equations) {
        graph = new int[26];
        for(int i=0; i<26; i++){
            graph[i]=i;
        }
        
        for(String eq : equations){
            if(eq.charAt(1)=='='){
                union(eq.charAt(0)-'a', eq.charAt(3)-'a');
            }
        }
        
        for(String eq : equations){
            if(eq.charAt(1)=='!'){
                if(connected(eq.charAt(0)-'a', eq.charAt(3)-'a')){
                    return false;
                }
            }
        }
        return true;
    }
    private void union(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        
        if(rootP!=rootQ){
            graph[rootP]=rootQ;
        }
    }
    
    private boolean connected(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }
    
    private int find(int p){
        while(graph[p]!=p){
            graph[p]=graph[graph[p]];
            p=graph[p];
        }
        
        return p;
    }
}