[笔记] 并查集

SpriteQAQ · 2024-08-17 10:28:43 · 算法·理论

1, 什么是并查集

并查集是一种很简洁的数据结构，主要作用于元素分类的问题，它存放了一堆一堆的不相交的集合，并可对其进行创建、查询和合并三种操作。

• 创建： 假如有n个元素，我们用一个数组a[n]来储存每一个元素的父亲节点（因为每个元素字可能有一个父亲节点），一开始我们要令它们的父亲节点为自己。

  int f[MAXN];        //f[i]表示i的父亲节点编号
  void init(int n){
    for (int i = 1; i <= n; i++){
        f[i] = i;   //父亲节点为自己
    }
  }

• 查询： 查询两个元素是否为同一集合 ( 我们可以判断祖宗节点是否相同 )。

  int f[MAXN];
  int find(int x){    //前置函数，用于寻找一个节点的祖宗节点
    if(f[x] == x) return x;
    else return find(f[x]);
  }
  bool is_contact(int x, int y){    //查询功能
    if(find(x) == find(y)) return 1;
    else return 0;
  }

• 合并： 将题目所描述的两个本不相关的元素合并成一个集合。

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

并查集最核心的思想在于用集合中的祖先元素来代表整个集合。

2, 合并优化

① 按轶合并

优化代码：

int find(int x){                    //前置函数，用于寻找一个节点的祖宗节点
    if(f[x] == x) return x;
    else return find(f[x]);
}
void merge(int x, int y){           //merge(x, y)表示将x, y的祖宗节点按轶合并 
    int rx = find(x), ry = find(y);
    if(rx == ry) return;
    if(deep[rx] <= deep[ry]){
        f[rx] = ry;
    }else if(deep[rx] > deep[ry]){
        f[ry] = rx;
    }
    if(deep[rx] == deep[ry]){
        deep[ry]++;
    }
    return; 
}

②路径压缩

优化代码：

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

③路径压缩+按轶合并

书接上回，那么路径压缩后每一个集合是否都是两层呢？ NO！
路径压缩是在find函数里进行的，只能压缩当前查询的路径，所以我们可以把二者结合起来。
优化代码：

int find(int x){                    //前置函数，用于寻找一个节点的祖宗节点
    if(f[x] == x) return x;
    else return f[x] = find(f[x]);  //路径压缩
}
void merge(int x, int y){           //按轶合并 
    int rx = find(x), ry = find(y);
    if(rx == ry) return;
    if(deep[rx] <= deep[ry]){
        f[rx] = ry;
    }else if(deep[rx] > deep[ry]){
        f[ry] = rx;
    }
    if(deep[rx] == deep[ry]){
        deep[ry]++;
    }
    return; 
}

3, 最终代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int f[MAXN], deep[MAXN];
void init(int n){
    for (int i = 1; i <= n; i++){
        f[i] = i;
    }
}
int find(int x){
    if(f[x] == x) return x;
    else return f[x] = find(f[x]);
}
void merge(int x, int y){
    int rx = find(x), ry = find(y);
    if(rx == ry) return;
    if(deep[rx] <= deep[ry]){
        f[rx] = ry;
    }else if(deep[rx] > deep[ry]){
        f[ry] = rx;
    }
    if(deep[rx] == deep[ry]){
        deep[ry]++;
    }
    return;
}
bool is_contact(int x, int y){
    if(find(x) == find(y)) return 1;
    else return 0;
}
int main(){

    return 0;
}