2020-06-08 至 2020-06-14 LeetCode 每日一题

[0608] 990. Satisfiability of Equality Equations (medium)

keyword: 并查集、图

no details process

并查集

并查集被很多OIer（OIer可理解成参加信息学竞赛的人或信息学竞赛(如CSP,NOI,IOI,CTS(C),APIO，甚至ACM）选手，或者也可以理解为信息学奥林匹克爱好者从事信息学研究的人。）认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作： - 合并（Union）：把两个不相交的集合合并为一个集合。 - 查询（Find）：查询两个元素是否在同一个集合中。

关于并查集的概念、优化，请参看这篇文章。

Question

Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: "a==b" or "a!=b". Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

Example 1:

1 2	`Input: ["a==b","b!=a"] Output: false`

Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second. There is no way to assign the variables to satisfy both equations.

Example 2:

1 2	`Input: ["b==a","a==b"] Output: true`

Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

Example 3:

1 2	`Input: ["a==b","b==c","a==c"] Output: true`

Example 4:

1 2	`Input: ["a==b","b!=c","c==a"] Output: false`

Example 5:

1 2	`Input: ["c==c","b==d","x!=z"] Output: true`

Note: 1 <= equations.length <= 500 equations[i].length == 4 equations[i][0] and equations[i][3] are lowercase letters equations[i][1] is either '=' or '!' equations[i][2] is '='

Intuition

并查集

我们可以将每一个变量看作图中的一个节点，把相等的关系 == 看作是连接两个节点的边，那么由于表示相等关系的等式方程具有传递性，即如果 a==b 和 b==c 成立，则 a==c 也成立。也就是说，所有相等的变量属于同一个连通分量。因此，我们可以使用并查集来维护这种连通分量的关系。

首先遍历所有的等式，构造并查集。同一个等式中的两个变量属于同一个连通分量，因此将两个变量进行合并。

然后遍历所有的不等式。同一个不等式中的两个变量不能属于同一个连通分量，因此对两个变量分别查找其所在的连通分量，如果两个变量在同一个连通分量中，则产生矛盾，返回 false。

如果遍历完所有的不等式没有发现矛盾，则返回 true。

具体实现方面，使用一个数组 parent 存储每个变量的连通分量信息，其中的每个元素表示当前变量所在的连通分量的父节点信息，如果父节点是自身，说明该变量为所在的连通分量的根节点。一开始所有变量的父节点都是它们自身。对于合并操作，我们将第一个变量的根节点的父节点指向第二个变量的根节点；对于查找操作，我们沿着当前变量的父节点一路向上查找，直到找到根节点。

时间复杂度：\(O(n + C \log C)\)，其中 \(n\) 是 equations 中的方程数量，\(C\) 是变量的总数，在本题中变量都是小写字母，即 \(C \leq 26\)。上面的并查集代码中使用了路径压缩优化，对于每个方程的合并和查找的均摊时间复杂度都是 \(O(\log C)\)。由于需要遍历每个方程，因此总时间复杂度是 \(O(n + C \log C)\)。

空间复杂度：\(O(C)\)。创建一个数组 parent 存储每个变量的连通分量信息，由于变量都是小写字母，因此 parent 是长度为 \(C\)。

参考链接

作者：LeetCode-Solution 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Code

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

    public void union(int[] parent, int index1, int index2) {
        parent[find(parent, index1)] = find(parent, index2);
    }

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