基本操作

初始化

并查集本质上就是通过数组来维护一个树结构，初始状态下集合中的每个元素都不相交，父节点设为自己。

int *fa = new int[n];


void init(int n)
{
    for (int i = 0; i < n; ++i) {
        fa[i] = i;
    }
}

合并

合并两个不相交的元素，实际上就是把他们放到一个树当中去。

void merge(int i, int j)
{
    // find用于找到某元素所在树的根节点
    fa[find(i)] = find(j); // 把元素i所在树的根节点接到j所在的根节点上去
}

查询（递归/非递归）

// 递归方式
int find(int x)
{
    if (fa[x] == x) {
        return x;
    } else {
        return find(fa[x]); // 如果x不是根节点，那么继续往上找
    }
}


// 迭代方式
int find(int x)
{
    while (fa[x] == x) {
        x = fa[x];
    }
    return x;
}

优化算法

上面写法是最原始的并查集算法，可能会导致查找的复杂度呈线性，当n非常大时，查找效率会变得很低。下面提供了两种优化的方法。

路径压缩

路径压缩是基于查找进行优化的，在查找的过程中将沿途查找过程中fa[x] != x的元素直接接到根节点上去。

int find(int x)
{
    if (fa[x] != x) {
        fa[x] = find(fa[x]);
    }
    return fa[x];
}

按秩合并

按秩合并是基于合并进行优化的，给每个树都维护自己的秩（树的高度），使得每次合并时，都是秩小的树合并到秩大的树，使得整个树相对平衡，查找时的时间复杂度就接近nlgn。

int *fa = new int[n];
int *rank = new int[n];

void init(int n)
{
    for (int i = 0; i < n; ++i) {
        fa[i] = i;
        rank[i] = 1; // 初始时秩为1
    }

}

void merge(int i, int j)
{
    int x = find(i);
    int y = find(j);
    if (x == y) { //如果在同一棵树上，直接退出
        return;
    }
    if (rank[x] < rank[y]) {
        fa[x] = y;
    } else {
        fa[y] = x;
        if (rank[x] == rank[y]) {
            rank[x]++;
        }
    }
}