侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【图, 并查集】等式方程的可满足性

GabrielxD
2022-05-23 / 0 评论 / 0 点赞 / 127 阅读 / 716 字
温馨提示:
本文最后更新于 2022-07-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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

提示:

  • 1 <= equations.length <= 500
  • equations[i].length == 4
  • equations[i][0]equations[i][3] 是小写字母
  • equations[i][1] 要么是 '=',要么是 '!'
  • equations[i][2]'='

解题

方法一:并查集

思路

把字母看作顶点,相等关系看作一条边,构建出一个无向图,那么由于表示相等关系的等式方程具有传递性,即如果 $a==b$ 和 $b==c$ 成立,则 $a==c$ 也成立。也就是说,所有相等的变量属于同一个连通分量。因此,使用并查集来维护这种连通分量的关系。 首先遍历所有的等式,构造并查集。同一个等式中的两个变量属于同一个连通分量,因此将两个变量进行合并。 然后遍历所有的不等式。同一个不等式中的两个变量不能属于同一个连通分量,因此对两个变量分别查找其所在的连通分量,如果两个变量在同一个连通分量中,则产生矛盾,返回 false。 如果遍历完所有的不等式没有发现矛盾,则返回 true

代码

class Solution {
    private static final int SIZE = 26;
    private int[] unionFind;

    public boolean equationsPossible(String[] equations) {
        unionFind = new int[SIZE];
        for (int i = 0; i < SIZE; i++) unionFind[i] = i;
        for (String equation : equations) {
            if (equation.charAt(1) == '=') {
                union(equation.charAt(0) - 'a', equation.charAt(3) - 'a');
            }
        }
        for (String equation : equations) {
            if (equation.charAt(1) == '!' &&
                find(equation.charAt(0) - 'a') == find(equation.charAt(3) - 'a')) {
                return false;
            }
        }
        return true;
    }

    private void union(int p, int q) {
        unionFind[find(p)] = find(q);
    }

    private int find(int n) {
        if (n != unionFind[n]) unionFind[n] = find(unionFind[n]);
        return unionFind[n];
    }
}
0

评论区