题目

在这里插入图片描述

解题

参考：

并查集

概念及应用

在这里插入图片描述

优化（路径压缩）

在这里插入图片描述

按秩合并可以参考：「手画图解」手写UnionFind，并查集不再畏惧

代码

在这里插入图片描述

// javascript
var equationsPossible = function(equations) {
    const parent = new Array(26);
    // 初始化时指向自己
    for (let i = 0; i < 26; i++) parent[i] = i;
    const codeOfA = 'a'.charCodeAt();
    for (const str of equations) {
        if (str.charAt(1) === '=') {
            const index1 = str.charCodeAt(0) - codeOfA;
            const index2 = str.charCodeAt(3) - codeOfA;
            union(parent, index1, index2);
        }
    }
    for (const str of equations) {
        if (str.charAt(1) === '!') {
            const index1 = str.charCodeAt(0) - codeOfA;
            const index2 = str.charCodeAt(3) - codeOfA;
            // 如果根节点相同，表明在一个集合里面，即是相等的关系
            if (find(parent, index1) === find(parent, index2)) {
                return false;
            }
        }
    }
    return true;
};

// 把一个集合的根节点指向另一个集合的根节点
const union = (parent, index1, index2) => {
    parent[find(parent, index1)] = find(parent, index2);
};

// 隔代路径压缩
const find = (parent, index) => {
    while (parent[index] !== index) {
        parent[index] = parent[parent[index]];
        index = parent[index];
    }
    return index;
};