leetcode-990.等式方程的可满足性

题目

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

样例输入输出

示例 1：
输入：["a==b","b!=a"]
输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
示例 2：
输出：["b==a","a==b"]
输入：true
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
示例 3：
输入：["a==b","b==c","a==c"]
输出：true
示例 4：
输入：["a==b","b!=c","c==a"]
输出：false
示例 5：
输入：["c==c","b==d","x!=z"]
输出：true

解题思路

这一题我们需要用到并查集的思想，没有并查集的基础这里建议先看这个简单了解并查集
我们根据题意，可以把相等的数进行集合合并，最后再处理不相等的数。我们是可以发现的，如果没有不等于的情况的话，我们的方程是永远成立。相关的做法有两点比较重要就是

• 我们要对方程进行分类，把不等于的保留起来。把等于的直接进行合并
• 我们从不等于的方程里面一个一个取出来，对符号两边的数进行查找，如果他们的根结点不同的话，那么不等于就是成立的，这个我们不管。但是如果根结点相同的话，而他们的符号又是不等于的话，那么这就是不成立的，对于这种情况我们直接返回false,方程不成立。

我们以示例4为例画个图认识一下
我们首先将所有成立的情况拿出来构建集合

图1.0
然后在不等的列表中取出b!=c的方程，我们可以发现

father[b] = a;  //b的根结点是a
father[c] = a;  //c的根结点是a

它们应该是成立的，而它们的符号却是!=，那么只能说方程是不成立的！
具体实现代码如下：

class Solution {
    //定义一个可以容纳所有字符的数组当作并查集合
    private int[] father = new int[255];
    public boolean equationsPossible(String[] equations) {
        if(equations.length < 1) return true;
        init();
        //初始化一个不等于方程的列表，我们首先将不等于的存起来，等于的直接进行处理掉
        List<String> noEqualList = new ArrayList<>(); 
        //如果全是等于的话，那么永远成立
        for(int i = 0; i < equations.length; i++){
            String s = equations[i];
            if(s.charAt(1) == '!'){  //如果是不等的话，我们就添加进不等的列表待后面处理
                noEqualList.add(s);
            }else{  //如果相等的话，我们直接对元素进行合并
                int a = s.charAt(0) - '0';
                int b = s.charAt(3) - '0';
                unionFather(a,b);
            }
        }
        //对于不等于的话，如果他们有相同的根节点的话，但是因为是!=,我们就说这个方程是不成立的
        for(int i = 0; i < noEqualList.size(); i++){
            String s = noEqualList.get(i);
            int a = s.charAt(0) - '0';
            int b = s.charAt(3) - '0';
            if(findFather(a) == findFather(b)) return false; 
        }
        return true;        
    }
    //查找根节点
    private int findFather(int x){
        int a = x;
        while(x != father[x]){
            x = father[x];
        }
        //路径压缩,把路径中的所有节点的父亲节点都改为根节点
        while(a != father[a]){
            int z = a;
            a = father[a];
            father[z] = x;
        }
        return x;
    }
    //合并根节点
    private void unionFather(int a,int b){
        int faa = findFather(a);
        int fab = findFather(b);
        father[faa] = fab;
    }
    //进行初始化，让每一个点的初始根节点都是它自己
    private void init(){
        for(int i = 0; i < father.length; i++){
            father[i] = i;
        }
    }
}