【每日算法Day 8】等式方程的可满足性

题目链接

LeetCode 990. 等式方程的可满足性 (opens new window)

题目描述

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。 

解题思路

由于“相等”这一关系具有传递性，相等的变量属于一个集合，并且只关心连通性而不关心距离，因此容易想到使用并查集来解。

并查集ADT的定义与适用范围：

并查集又称为不相交集合，用于判断一对元素是否相连，他们的关系是动态添加的而不是一开始就能直接确定的，这类问题称为动态连通性问题。例如求图的最小生成树的kruskal算法其实就用到了并查集。
并查集的主要操作有：“Union：合并”和“Find：查询是否在同一集合”。
并查集底层的数据结构为数组或者哈希表，用于表示“一个节点”指向的“父节点”，初始化时指向自己。
“合并”操作就是把一个集合的根节点指向另一个集合的根节点，只要两个节点的根节点相同就表示在同一节点中。这种表示不相交集合的方法称为“代表元法”，以每个节点的根节点作为一个集合的代表元。

下面就来看如何表示并查集以及如何进行合并和查找。

无论是使用数组（下标->值）还是哈希表（key->value）都是表示节点与父节点的指向关系，使用并查集最终将输入表示为多个树组成的森林。树的高度越大查询的效率就越低，故需对并查集进行优化。

1. 路径压缩（隔代压缩/完全压缩）
隔代压缩：对于集合中最深的点，将其指向其父亲的父亲，并对其父亲的父亲执行相同动作直到根节点；完全压缩：将除根节点以外的所有节点指向根节点，需要借助递归执行，效率低一些但压缩完查询效率更高。

2. 按秩合并（发生在合并过程中）
在合并过程中使高度更小的树的根节点指向高度更大的根节点，以避免合并以后的树高度增加。

路径压缩会改变原来树的高度，如果和按秩合并同时使用会使得后者的秩定义不易于维护，不好分析时间复杂度。两者同时使用时“合并”与“查询”的时间复杂度接近于O(1)，一般而言使用其中一个即可。

接下来给出解题逻辑：首先扫描一遍输入数组中的等式，将相等的点纳入同一个集合中。再扫描所有的不等式，检查所有的不等式中的两个值是否在同一集合中，发现有则返回false，扫描完都没有在同一集合中的则返回true。

public boolean equationsPossible(String[] equations) {
    UnionFind uf=new UnionFind(26);
    for (String equation : equations) {
        if (equation.charAt(1) == '=') {
            uf.union(equation.charAt(0)-97,equation.charAt(3)-97);
        }
    }
    for (String equation : equations) {
        if (equation.charAt(1) == '!' && uf.find(equation.charAt(0)-97)==uf.find(equation.charAt(3)-97)) {
            return false;
        }
    }
    return true;
}

//内部类，并查集
private class UnionFind {
    private int[] parent;

    //构造时，parent指向自身
    public UnionFind(int length) {
        parent=new int[length];
        for (int i = 0; i < length; i++) {
            parent[i]=i;
        }
    }

    //一次find过程也是做一次隔代压缩
    public int find(int index) {
        while (index != parent[index]) {
            parent[index]=parent[parent[index]];
            index=parent[index];
        }
        return index;
    }

    //合并操作直接修改root，由于上面使用了路径压缩这里就不再按秩合并了
    public void union(int x, int y) {
        int rootX=find(x);
        int rootY=find(y);
        parent[rootX]=rootY;
    }
}