并查集

  1. 初始化
    把每个点所在集合初始化为自身

    通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度为O(n)。
  2. 查找
    查找元素所在的集合，即根节点。
  3. 合并
    把元素所在集合合并为一个集合。

    通常来说

990. 等式方程的可满足性：


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



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



示例 1：



输入：["ab","b!=a"]

输出：false

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

var equationsPossible = function(equations) {
    let i = 0;
    let p = new Array(26).fill(0);
    p = p.map(item=>i++);//初始化
    
    function find(x){//标准并查集
        if(x === p[x]){
            return p[x];
        }else{
            p[x] = find(p[x]);
            return p[x];
        }
    }
    
    
    for(item of equations ){
        if(item[1] === '='){
            let r1 = find(item[0].charCodeAt()-'a'.charCodeAt());
            let r2 = find(item[3].charCodeAt()-'a'.charCodeAt());
            if(r1!=r2){
                p[r2] = r1;
            }
        }
    }
    
    for(item of equations){
        if(item[1] === '!'){
            let r1 = find(item[0].charCodeAt()-'a'.charCodeAt());
            let r2 = find(item[3].charCodeAt()-'a'.charCodeAt());
            if(r1===r2){
                return false;
            }
        }
    }
    
    return true;
    
};