Union Find算法

Union-Find算法也就是常说的并查集算法，主要用来解决图论中动态连通性问题。

连通具有以下几个性质：

1. ⾃反性：节点 p 和 p 是连通的。
2. 对称性：如果节点 p 和 q 连通，那么 q 和 p 也连通。
3. 传递性：如果节点 p 和 q 连通， q 和 r 连通，那么 p 和 r 也连通。

如上图所示，如果要将p、q连通，则可以把p的根结点连到q的根结点上，但是也会出现一个问题：如果每次都是随意的将一个节点的根结点连到另一个节点的根结点上，那么在查找节点的时候会导致O(n)的时间复杂度，而不是O(logn)。

对于⼀般的树可能出现极端不平衡的情况，使得树⼏乎退化成链表，树的⾼度最坏情况下可能变成N。为了解决此问题，我们其实是希望，⼩⼀些的树接到⼤⼀些的树下⾯，这样就能避免头重脚轻，更平衡⼀些。可以引用变量来计算每次需要合并的俩个子树的节点数，这样每次个数小的合并到个数大的根结点上，最终可以让整个数达到平衡树，时间复杂度可以降到O(logn)。

路径压缩可以进一步的压缩树的高度，使数高保持为常数，如下图所示：

990. Satisfiability of Equality Equations

​ 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:

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:

Input: ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

Example 3:

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

Example 4:

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

Example 5:

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

Note:

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

思路：

Union-Find

code：

/**
 * @param {string[]} equations
 * @return {boolean}
 */
var equationsPossible = function(equations) {
    const string='abcdefghijklmnopqrstuvwxyz',
          parent=Array(26),//父节点
          size=Array(26), //各个树的"重量"
          count=26; //连通分量个数
    for(let i=0;i<parent.length;i++) parent[i]=i;
    function union(p,q){ //合并
        let rootP=find(p),
            rootQ=find(q);
        if(rootP===rootQ) return;
        if(size[rootP]<size[rootQ]){
            parent[rootP]=rootQ;
            size[rootQ]+=size[rootP];
        }else{
            parent[rootQ]=rootP;
            size[rootP]+=size[rootQ];
        }
        // count--;
    }
    function connected(p,q){ //是否属于一个连通分量
        let rootP=find(p),
            rootQ=find(q);
        if(rootP===rootQ) return true;
        return false;
    }
    function find(x){ //路径压缩
        while(x!==parent[x]){
            parent[x]=parent[parent[x]];
            x=parent[x];
        }
        return x;
    }
    equations.forEach(str=>{
        let c1=str.charAt(0),
            c2=str.charAt(3),
            isEqual=str.charAt(1)==='='?true:false;
        let c1Index=string.indexOf(c1),
            c2Index=string.indexOf(c2);
        if(isEqual){
            union(c1Index,c2Index);
        }
    })
    for(let i=0;i<equations.length;i++){
        let str=equations[i];
        let c1=str.charAt(0),
            c2=str.charAt(3),
            isEqual=str.charAt(1)==='='?true:false;
        let c1Index=string.indexOf(c1),
            c2Index=string.indexOf(c2);
        if(!isEqual&&connected(c1Index,c2Index)){
            return false;
        }
    }
    return true;
};

总结：

使⽤ Union-Find 算法，主要是如何把原问题转化成图的动态连通性问题。对于算式合法性问题，可以直接利⽤等价关系，对于棋盘包围问题，则是利⽤⼀个虚拟节点，营造出动态连通特性。