简介

并查集是一种树形的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。

每个结点存储的是自己的父节点。

类型

weighted-union

存储权重信息：根节点存储的原本是-1，为了节省空间，可以把根节点存储的值乘上权重，例如权重为2的根节点，存储的值是-2；权重为3的根节点，存储的值是-3。

基本操作

find

1
2
3
4
5
6
7
int find(int x)
{
    if(x==parent[x])
        return x;
    else
        return find(parent[x]);
}

union

1
2
3
4
5
6
7
void union(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
        parent[fx]=fy;
}

其他union规则

  • 按照高度
  • 按照结点规模

    path compression 查找路径压缩

    路径压缩的本质是在查找返回的时候，将路径上的所有节点的父节点都指向根节点，这样可以减少后续查找的时间。
1
2
3
4
5
6
int find(int x)
{
    if(x!=parent[x])
        parent[x]=find(parent[x]);
    return parent[x];
}