并查集

zhou2023-10-072023-10-07

并查集

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

初始化

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

查询

我们需要沿着树向上移动，直至找到根节点。

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

路径压缩

为了避免形成链，优化查询的过程我们可以根据这个思路：把沿途的每个节点的父节点都设为根节点。去优化查询的过程，进行路径压缩。

int find(int x)
{
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);  //父节点设为根节点
        return fa[x];         //返回父节点
    }
}

插入

inline void merge(int i, int j)
{
    fa[find(i)] = find(j);
}

合并

要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点

inline void merge(int i, int j)
{
    fa[find(i)] = find(j);
}

在合并的过程中有个问题，就是左边合并右边还是右边合并左边，到底谁作为根节点的问题。虽然无论怎么合并都能得到正确的结果，但不同的链接方式会影响到时间复杂度，具体来说，如果我们将一棵点数与深度都较小的集合树连接到一棵更大的集合树下，显然相比于另一种连接方案，接下来执行查找操作的用时更小（也会带来更优的最坏时间复杂度）。

此外，我们对于合并后的结构其实也可以做部分的路径压缩，也可以按秩合并，（秩就是子节点到根节点的深度，就是离了多少层）

但在实际操作中，即便不去纠结怎么合并，代码也往往能够在规定时间内完成任务。所以其实没那么重要。