并查集（Disjoint Set Union，简称 DSU）是一种专门处理集合合并与连通性查询问题的高效数据结构，是算法竞赛、图论问题里的 “神器”。
一、并查集能干嘛？
它核心解决两个问题：
- 合并（Union/Merge）：把两个独立的集合，合并成一个集合。
- 查询（Find）：判断两个元素是否属于同一个集合（连通性判断）。
举个生活例子：
- 班级里一开始每个人都是自己的 “小组”。
- 老师让你和同桌组队，就是 “合并两个集合”。
- 你想知道自己和隔壁班的同学是不是同一个小组，就是 “查询连通性”。
它的优势是：在几乎常数的时间复杂度内，完成合并和查询操作，效率极高
二、代码实现
#include<iostream> using namespace std; const int N = 1e5; // 定义最大数据规模：100000 int fa[N]; // 核心数组：fa[x] 表示元素x的父节点 // 带路径压缩的查找函数：找x所在集合的根节点 int find(int x){ // 如果x的父节点是自己，说明它就是根节点，直接返回x // 否则：递归找父节点的根，并把x的父节点直接指向根（路径压缩） return fa[x]==x ? x : fa[x] = find(fa[x]); } // 合并函数：把元素a和元素b所在的集合合并 void merge(int a, int b){ // 找到a的根节点，再找到b的根节点 fa[find(a)] = find(b); } // 初始化函数：每个元素初始时都是自己的父节点（独立集合） void pre(int n){ for(int i=1; i<=n; i++){ fa[i] = i; } } int main(){ // 示例：测试并查集功能 int n = 5; pre(n); // 初始化：1-5每个元素自成集合 merge(1, 2); // 合并1和2 merge(2, 3); // 合并2和3（此时1、2、3在同一集合） merge(4, 5); // 合并4和5（此时4、5在同一集合） // 查询1和3是否连通 if(find(1) == find(3)){ cout << "1和3在同一个集合里！" << endl; }else{ cout << "1和3不在同一个集合里！" << endl; } // 查询1和4是否连通 if(find(1) == find(4)){ cout << "1和4在同一个集合里！" << endl; }else{ cout << "1和4不在同一个集合里！" << endl; } return 0; }#include<iostream> using namespace std; const int N=1e5; int fa[N]; int find(int x){ return fa[x]==x?:fa[x]=find(fa[x]); } void merge(int a,int b){ fa[find(a)]=find(b); } void pre(int n){ for(int i=1;i<=n;i++)fa[i]=i; } //如果find(x)==find(y)就说明x和y同属一个集合四、并查集常见应用场景
- 图论连通性问题：判断两个节点是否连通、统计无向图的连通分量个数。
- 最小生成树（Kruskal 算法）：判断边的两个端点是否已经连通，避免形成环。
- 动态连通性问题：比如好友关系、网络连接的动态合并与查询。
- 其他变种：带权并查集（比如处理食物链、距离问题）、可撤销并查集（离线处理问题）。
五、DSU总结
并查集的核心就是三个部分：
- 初始化：每个元素自成集合。
- 查找 + 路径压缩：找根节点，同时把路径上的节点直接指向根。
- 合并：把两个集合的根节点连起来。
六、逆元
//费马小定理，快速幂求逆元 typedef long long ll; ll qpow(ll a, ll b, ll mod) { ll res = 1; while(b) { if(b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } // 费马逆元：p必须是质数 //费马小定理，使用前提是p是质数，且整数a不是p的倍数（gcd(a,p)==1） ll inv(ll a, ll p) { return qpow(a, p - 2, p); }typedef long long ll; // 扩展欧几里得 ll exgcd(ll a, ll b, ll &x, ll &y) { if(!b) { x = 1; y = 0; return a; } ll d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } // 扩欧求逆元，a,p互质即可，p不必为质数。通用 ll inv_exgcd(ll a, ll p) { ll x, y; exgcd(a, p, x, y); x = (x % p + p) % p; return x; }const int N = 1e5 + 10; ll inv[N]; // 线性预处理1~n所有逆元，p为质数 void init_inv(int n, ll p) { inv[1] = 1; for(int i = 2; i <= n; i++) inv[i] = (p - p / i) * inv[p % i] % p; } //线性递推求逆元（批量求 1~n 逆元）七、求逆元三种方法怎么选？
- 只求单个逆元、模数是质数→ 费马小定理（最快好写）
- 模数不是质数，但互质→ 扩展欧几里得
- 要批量预处理 1~n 逆元→ 线性递推
