概述

并查集（Union-Find）用来合并集合和查找集合，但不支持分割集合。

算法

从集合中选择一个元素代表该集合，称该元素为该集合的代表元。

集合中的所有元素被组织成以代表元为根的树形结构。并且使用双亲表示法表示该树。

常用操作：

• 判断 x 所在的集合

Node findRoot(x) {
    node = x;
    while (node.getParent() >= 0)
        node = node.getParent();
    return node;
}

• 判断 x 和 y 是否属于同一个集合

boolean isInOneSet(x, y) {
    return findRoot(x) == findRoot(y);
}

• 合并集合

因为 findRoot() 方法的时间复杂度与树的深度是成正比，所以在合并集合时，应该尽量减少合并后的树的深度，这个过程叫路径压缩。

因为在树的双亲表示法中，根节点的父索引是一个负值，所以可以使用这该值表示该树的深度。在合并时，将较浅的树合并到较深的树。

union(x, y) {
    rootX = findRoot(x);
    rootY = findRoot(y);
    if (rootX == rootY)
        return;

    depthX = -1 * rootX.getParent();
    depthY = -1 * rootY.getParent();
    if (depthX == depthY) {
        rootY.setParent(rootX);
        rootX.setParent(rootX.getParent() - 1);
    } else if (depthX < depthY) {
        rootX.setParent(rootY);
    } else {
        rootY.setParent(rootX);
    }
}

例子

题目名称：

等式方程的可满足性

原题地址：

leetcode 地址

题目描述：

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

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

Python 实现：

# coding: utf8


class Node(object):
    def __init__(self):
        self.parent = -1


class UnionFindSet(object):
    def __init__(self):
        self._nodes = [Node() for _ in range(27)]

    def find_root(self, x):
        temp = x
        while self._nodes[temp].parent >= 0:
            temp = self._nodes[temp].parent
        return temp

    def merge(self, x, y):
        si = self.find_root(x)
        sj = self.find_root(y)
        if si == sj:
            return

        node_i = self._nodes[si]
        depth_i = -1 * node_i.parent
        node_j = self._nodes[sj]
        depth_j = -1 * node_j.parent

        if depth_i >= depth_j:
            self._nodes[sj].parent = si
            self._nodes[si].parent = -1 * max(depth_i, depth_j+1)
        else:
            self._nodes[si].parent = sj
            self._nodes[sj].parent = -1 * max(depth_j, depth_i+1)


class Solution(object):
    def equationsPossible(self, equations):
        """
        :type equations: List[str]
        :rtype: bool
        """
        ufs = UnionFindSet()

        for equation in equations:
            if equation[1] != "=":
                continue
            ufs.merge(
                ord(equation[0])-ord("a"),
                ord(equation[3])-ord("a"))

        for equation in equations:
            if equation[1] != "!":
                continue
            if ufs.find_root(ord(equation[0])-ord("a")) == \
                    ufs.find_root(ord(equation[3])-ord("a")):
                return False

        return True


if __name__ == "__main__":
    equations = ["a==b", "b==c", "a==c", "e==f", "a!=c"]
    solution = Solution()
    print(solution.equationsPossible(equations))