并查集（学习笔记）

XichenOC · 2024-10-18 13:40:37 · 算法·理论

用处：

并查集是一种用来处理不同集合之间的关系的算法。正如它名字一样它本身就是一个可以合并，查询的树形集合。它可以用来做分组类型的题。具体功能，拓展和原理

实现：

基本功能的实现：

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

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

void merge(int x,int y){
    if(find(x)==find(y))return;
    fa[find(x)]=find(y);
}

练习：

1.P1111 修复公路 题解
2.P1525 [NOIP2010 提高组] 关押罪犯 题解
3.Cheap Robot 题解