M28276: 判断等价关系是否成立

disjoint set, http://cs101.openjudge.cn/practice/28276/

输入若干行关于变量间的关系的字符串，其中每个字符串的长度为4，可以采取两种不同的形式xi==yi 或 xi!=yi。这里，xi 和 yi 是小写字母（不一定不同），代表单个字母的变量名。请你编写一个程序判断是否有可能为变量名分配整数以满足所有给定的等式。

输入

第一行：正整数 n<50, 代表输入的字符串数量。第二行：n个长度为4的字符串，采取两种不同的形式xi==yi 或 xi!=yi，xi 和 yi 是小写字母（不一定不同）。

输出

如果存在分配的可能，打印 True，反之，打印 False。

样例输入

sample1 input:
2
a==b
b!=a

sample1 output:
False

解释：如果指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

样例输出

sample2 input:
2
a==b
b==a

sample2 output:
True

可以指定 a = 1 且 b = 1 以满足满足这两个方程。

提示

tags: disjoint set (并查集)

来源

zht, https://leetcode.com/problems/satisfiability-of-equality-equations/

第一遍：处理所有 == 表达式，执行 union。

第二遍：处理所有 != 表达式，检查 find(x) 是否等于 find(y)，若相等则冲突。

python

def main():
    n = int(input().strip())
    equations = [input().strip() for _ in range(n)]
    
    parent = list(range(26))
    
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        rx, ry = find(x), find(y)
        if rx != ry:
            parent[ry] = rx
    
    # 第一次遍历：处理所有等式
    for eq in equations:
        if eq[1] == '=':  # "a==b"
            x = ord(eq[0]) - ord('a')
            y = ord(eq[3]) - ord('a')
            union(x, y)
    
    # 第二次遍历：检查不等式
    for eq in equations:
        if eq[1] == '!':  # "a!=b"
            x = ord(eq[0]) - ord('a')
            y = ord(eq[3]) - ord('a')
            if find(x) == find(y):
                print(False)
                return
                
    print(True)

if __name__ == "__main__":
    main()

M28276: 判断等价关系是否成立 ​

M28276: 判断等价关系是否成立