概述

并查集(Union-Find)用来“合并集合” 和 “查找集合”。但是不支持分割集合


算法

从集合中选择一个元素代表该集合,该元素为该集合的代表元
一个集合中所有的元素都被组织成以代表元为根的树形结构。并且使用双亲表示法来表示。
常用的操作:

Node findRoot(x) {
    node = x;
    while (node.getParent() >= 0)
        node = node.getParent();
    return node;
}
boolean isInOneSet(x, y) {
    return findRoot(x) == findRoot(y);
}
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);
    }
}

在本文的例子中,使用的是链式存储结构,也可以使用数组这种顺序存储结构来实现并查集。本文不再赘述。


应用