---
title: 990. Satisfiability of Equality Equations
tags: graph
description: share source code.
---

# 990. Satisfiability of Equality Equations

class Solution {

    static class UnionFind{
        int root []; 
        int rank [];
        int component;
        

        public UnionFind(int n){
            this.root = new int [n];
            this.rank = new int [n];
            this.component = n;
            
            for(int i = 0; i < n; i++){
                root [i] = i;
                rank [i] = 1;
            }

        } 

        public boolean isConnected(int u, int v){
            return find(u) == find(v);
        }

        public void merge(int u, int v){
            int pu = find(u); 
            int pv = find(v);
            if(rank[pu] < rank[pv]){
                root [pu] = pv;
            }else if(rank[pu] > rank[pv]){
                root [pv] = pu;
            }else{
                root [pv] = pu;
                rank [pu]++;
            }
             component--;
        }

        public int find(int u){
            while(u != root[u]){
                root[u] = root[root[u]];
                u = root[u];
            }
            return u;
        } 
    }


    public boolean equationsPossible(String[] equations) {
        UnionFind uf = new UnionFind(256);

        for(String equation : equations){
         
            String [] points = equation.split("==");
            // System.out.print(Arrays.toString(points) +":" + points.length );
            if(points.length == 2){
                int a = (int)(points[0].charAt(0) - 'a');
                int b = (int)(points[1].charAt(0) - 'a');
                if(!uf.isConnected(a, b)){
                    uf.merge(a, b);
                }
                //
            }
        }

        for(String equation : equations){
            String [] points = equation.split("!=");
          
            if(points.length == 2 ){
                int a = (int)(points[0].charAt(0) - 'a');
                int b = (int)(points[1].charAt(0) - 'a');
                if(uf.isConnected(a, b)){
                    return false;
                 }    
                
            }
        }
        return true;
    }
}