算法

(并查集) $O(N)$

并查集模版题。把所有相等的变量都放到同一个集合中，然后去检查不等的关系，对于每个不等的方程，去检查两个变量是否在同一个集合中，如果是的话说明之前已经找到过他们相等的关系，那么就找到矛盾了，直接返回$false$，反之就不矛盾，然后一直$check$下去，如果一直没找到矛盾就返回$true$。

Java 代码

class Solution {
    public boolean equationsPossible(String[] equations) {
        int[] parent = new int[26];
        for (int i = 0; i < 26; ++i) parent[i] = i;

        // union
        for (String s : equations) {
            if (s.charAt(1) == '!') continue;
            int l = s.charAt(0) - 'a';
            int r = s.charAt(3) - 'a';
            union(parent, l, r);
        }

        // check unequal
        for (String s : equations) {
            if (s.charAt(1) == '=') continue;
            int l = s.charAt(0) - 'a';
            int r = s.charAt(3) - 'a';
            if (find(parent, l) == find(parent, r)) return false;
        }

        return true;
    }

    public void union(int[] parent, int a, int b) {
        int ap = find(parent, a);
        int bp = find(parent, b);
        parent[bp] = ap;
    }

    public int find(int[] parent, int a) {
        while (parent[a] != a) {
            parent[a] = parent[parent[a]];
            a = parent[a];
        }
        return parent[a];
    }
}