LeetCode力扣990题：等式方程的可满足性（并查集详解）

末蓝、 2023-02-16 06:58 44阅读 0赞

题目：

> 给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 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
    
    提示：
    1 <= equations.length <= 500
    equations[i].length == 4
    equations[i][0] 和 equations[i][3] 是小写字母
    equations[i][1] 要么是 '='，要么是 '!'
    equations[i][2] 是 '='

这个题就是要用 **并查集** 来做，思想很有用。

### 一、并查集是什么？ ###

从英文名字来看也就是，**不重叠** 的集合。

他是并支持 **合并** 与 **查询** 两种操作的一种数据结构。为什么会产生这种数据结构呢？

我们先来看这样一个问题：

> 若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求**任意给出的两个人是否具有亲戚关系**。  
>   
> 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

这个问题如果用实际情况来看，我们把所有人划分到若干个不相交的集合中，每个集合里的人 **彼此是亲戚**，显然这就是 **“ 家 ”** 的概念，为了判断两个人是否为亲戚，只需看它们是否属于同一个大 **“ 家 ”** 即可。

（但是这个问题也不能太实际，太实际的话，亲戚关系传递下去，很可能天下一家了）

到这里，并查集这个数据结构的引入就很容易理解了。

这种数据结构里，开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，最终就划分好了，拥有了一堆，**不重叠的集合**。

对于两个人是否为亲戚，只要判断他们是否在同一个集合里即可。

在 **创建并查集** 的过程中，一个一个元素的加入，显然需要两个操作：

1.  **查:** 对于某一个元素，我们得判断是否已经存在某一个集合是他应该加入的；
2.  **并:** 如果这个元素和现在已有的某个元素应该属于同一个集合，那就把他加进去。
3.  如果“查”的结果为假，那当前元素暂时先是自己独立的集合。

以上我们只是在逻辑上说明了这件事，具体实现起来，方法也有很多，一般维护这个“集合”用的实现是 **哈希表或者数组**。

添加元素的 “ 并 ” 操作 **最简单** 直接的是单链表，一个链表表示一个集合，但是如果要判断一个新元素的“查”的过程就很慢，也就是有 n 个元素的集合整体在逻辑上是一个，深度为 n 的树。  
如下图，0 1 2 3 4 依次的合并就会是这样：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]  
我们希望优化这个树，让他的深度 <n 。这样就能在 “查” 的过程更搞笑一些。让新加入集合里面的元素尽量都靠近根节点，具体操作是：需要在 **“ 查 ” 过程**中同时更改节点的指针指向。这个过程叫做 **“ 路径压缩 ”** （另一种是优化方式是按秩合并，不常用）具体可以参考这篇知乎的文章：  
https://zhuanlan.zhihu.com/p/93647900

### 二、等式方程的可满足性 ###

回到这个题目，里面有一个很突出的点，那就是 **“ == ”** 的判断，相等是具有 **传递性** 的，所以我们容易想到用并查集来解决这个问题，思路也很简单。

*  对于所有的字母 **等式** 来说，我们利用并查集创建出来若干个集合，也就是若干棵树。
 *  对于剩下的字母 **不等式** 来说，如果 *不等式两边的字母* 出现了同一个集合里，那就出现了矛盾，返回 false。
 *  如果遍历完不等式，没出现矛盾，那就返回true。

具体实现，我们选择 **数组** ，由于字母只有 26 个，是有限的，那么某个字母 x 等于另一个字母 y ，这样的过程用数组下标和元素的对应关系来表示，一个长度为 26 的数组就足够了，哪怕再多重复的相等关系，这个数组里都能表示，因为**传递**。

刚才我们提到了在 **“ 查 ”** 的过程中的优化：**路径压缩**。路径压缩一般有两种：隔代压缩 和 完全压缩 。

**隔代压缩**  
如果本来的树是 4->3->2->1->0。我们可以让： node.parent=node.parent.parent。

这样一来，4->2，2->0，执行完之后树的高度就会降低，因此在“查”的过程，“判断是否属于同一个根节点”时间会尽量短：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70 1]

很显然，这种方式在代码层面上（以数组实现为例）也只用加上一行：

parent[x]=parent[parent[x]];//parent 指向 x 换为 parent 指向 x 的指向

**完全压缩**  
完全压缩也就是希望把所有的元素都指向同一个根节点，这样 “查” 的过程， “是否属于同一个根节点” 的判断就会很快。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70 2]  
仍然是 4->3->2->1->0 这个例子，我们在操作的时候就要让

> 4.parent=4.parent.parent.parent.parent;  
> 3.parent=3…parent.parent.parent;  
> 2.parent=2…parent.parent;

显然在代码层面需要借助**递归**，压缩过程就不会那么高效。

#### 本题我们采用数组存储+隔代压缩。 ####

###### 1.初始化： ######

int[] sets=new int[26];//保存字母关系的集合
            for(int i=0;i<26;i++){
        
                sets[i]=i;//初始时所有的字母指向本身
            }

###### 2.解析所有 等式 ，并进行 union 操作，也就是并进数组去，让相等的各自都成为一个集合。 ######

for(String expr:equations){
        
                //对于所有的等式进行合并
                if(expr.charAt(1)=='='){
        
                    int letter1=expr.charAt(0)-'a';
                    int letter2=expr.charAt(3)-'a';
                    //对两个字母，调用union方法并进 sets 里面
                    union(sets,letter1,letter2);
                }
            }

这里巧妙利用每个字母和 ‘a’ 的 ASCII 的差值，来对应到 0~25 的位置。

union 方法需要实现，我们单独写一个方法在下面：

1. 先“查”，查到其中一个所在的集合的根节点，那就要用到 find 方法；
    2. 再“并”，直接用找到的根节点位置进行赋值。

//并查集的并，将相等关系的两个字母合并到一个集合
        public void union(int[] sets,int letter1,int letter2){
        
            //我们以 letter1 的根节点为基准，把 letter2 的根合并到 letter1 的根
            sets[find(sets,letter2)]=find(sets,letter1);
        }

套娃来了，实现“并”的方法里面是先进行了 “ 查 ” ，所以 find 方法 也需要我们实现，而查找的过程也要同时进行 隔代压缩 ：

//并查集的查，根据 letter 找到他所在集合的根节点
        public int find(int[] sets,int letter){
        
            int index=letter;
            //在一个树里，只有根节点是自己指向自己 ，即 sets[index]=index
            while(sets[index]!=index){
        
                sets[index]= sets[ sets[index] ];//同时进行了隔代压缩
                index =sets[index];
            }
            return index;
        }

这里注意，隔代压缩的过程，在查找某个节点的根节点的过程中， 如果它本身不是根节点，那么他 while 循环里就会执行压缩：

1.  如果执行一步之后，满足while条件 sets\[index\] = index，那么说明要合并的节点就是根节点的孩子，此时 sets\[index\]= sets\[ sets\[index\] \] 没有带来任何改变；
2.  两步及以上之后满足while条件 sets\[index\] = index，那么在 while 循环里，每一次向上查找根节点的同时， index 节点的父节点也在变化，这就达到了隔代压缩的目的。

###### 3.解析所有不等式 ，利用等式的并查集判断是否有矛盾产生 ######

矛盾的判断方式就是，调用 “ 查 ” 方法，如果各自的根节点是一样的，那么说明出现在了同一个集合里，和 “ 不等式 ” 是矛盾的。

//对于不等式，查找是否存在矛盾
            for(String expr:equations){
        
                if(expr.charAt(1)=='!'){
        
                    int letter1=expr.charAt(0)-'a';
                    int letter2=expr.charAt(3)-'a';
                    //对两个字母，查找各自的index，如果相等，则false
                    if(find(sets,letter1)==find(sets,letter2)){
        
                        return false;
                    }
                }
            }

###### 4.没有发现矛盾，返回 ######

return true;

###### 最后，我们组合代码 ######

class Solution {
        
        public boolean equationsPossible(String[] equations) {
        
            int[] sets=new int[26];//保存字母关系的集合
            for(int i=0;i<26;i++){
        
                sets[i]=i;//初始时所有的字母指向本身
            }
    
            //每一个式子形如 a==b 或者 a!=b
            for(String expr:equations){
        
                //对于所有的等式进行合并
                if(expr.charAt(1)=='='){
        
                    int letter1=expr.charAt(0)-'a';
                    int letter2=expr.charAt(3)-'a';
                    //对两个字母，调用union方法并进 sets 里面
                    union(sets,letter1,letter2);
                }
            }
    
            //对于不等式，查找是否存在矛盾
            for(String expr:equations){
        
                if(expr.charAt(1)=='!'){
        
                    int letter1=expr.charAt(0)-'a';
                    int letter2=expr.charAt(3)-'a';
                    //对两个字母，查找各自的index，如果相等，则false
                    if(find(sets,letter1)==find(sets,letter2)){
        
                        return false;
                    }
                }
            }
            return true;
        }
    
        //并查集的并，将相等关系的两个字母合并到一个集合
        public void union(int[] sets,int letter1,int letter2){
        
            //我们以 letter1 的根节点为基准，把 letter2 的根合并到 letter1 的根
            sets[find(sets,letter2)]=find(sets,letter1);
        }
    
        //并查集的查，根据 letter 找到他所在集合的根节点
        public int find(int[] sets,int letter){
        
            int index=letter;
            //在一个树里，只有根节点是自己指向自己 ，即 sets[index]=index
            while(sets[index]!=index){
        
                sets[index]= sets[ sets[index] ];//同时进行了隔代压缩
                index =sets[index];
            }
            return index;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200609131614908.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200609133259359.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200609133404726.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA5Mjc4Nw==,size_16,color_FFFFFF,t_70