https://leetcode.com/problems/satisfiability-of-equality-equations/

satisfiability-of-equality-equations.java

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