数据结构-并查集

并查集

参考资料:并查集 - OI Wiki

基本概念

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

显然，并查集支持两种操作:

  • 合并(union): 合并两个元素各自所属的集合
  • 查询(find): 查询某个元素所属的集合

初始化

初始时，每个元素都位于一个单独的集合表示为一棵只有根节点的树。方便起见，我们将根节点的父亲设为自己。

1
2
vector<int> fa;
for(int i=0;i<=n;i++) fa[i]=i;

查询

我们需要沿着树向上移动，直至找到根节点。由于根节点的父亲是自己本身，因此递归的终止应该是fa[x] == x。

1
2
3
int find(int x){
	return fa[x] == x? x: find(fa[x]);
}

路径压缩

查询操作的目的是找到该元素的根节点，它和其它元素如何联系并不重要。因此，我们可以将查询过程中的每个元素直接连接到根节点（更改其父节点为根节点），减小了树的深度，加快了后续查询。

1
2
3
int find(int x){
	return fa[x] == x? x: (fa[x] = find(fa[x]);
}

合并

朴素的合并，只要找到两个元素对应的根节点，让其中一个为另一个的子节点即可。特殊的，可以通过集合的大小或者秩进行启发式合并。

1
2
3
4
5
6
7
8
9
10
11
//按集合大小
vector<int> siz(n+1,1); //用于存储集合大小，只让根节点准确表示
void unite(int x,int y){
    x=find(x),y=find(y);
    if(x==y) return;
    if(siz[x]>siz[y]){ //让小的节点x，接入以y为根的树
        swap(x,y);
    }
    fa[x] = y;
    siz[y] += siz[x];
}

参考实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> fa;
vector<int> size;

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

void unite(int x,int y){
    x = find(x),y = find(y);
    if(x!=y){
        if(size[x]<size[y]){
            swap(x,y); 
        }
        fa[y] = x;
        size[x] += size[y];
    }
}

出于一定需要，并查集也可以用结构体的形式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct dsu{
    vector<int> fa,siz;
    dsu (int size):fa(size),siz(size,1){
        for(int i=0;i<size;i++){
            fa[i] = i;
        }
    }
    int find(int x){
        if(fa[x]==x) return x;
        else return fa[x]=find(fa[x]);
    }
    void unite(int x,int y){
        x = find(x),y = find(y);
        if(x==y) return;
        if(siz[x]>siz[y]){
            swap(x,y);
        }
        fa[x] = y;
        siz[y] += siz[x];
    }
}