并查集作用处理集合合并、查询两点是否属于同一集合常用于连通性问题。 核心两个操作find(x)找 x 的根带路径压缩缩短查询路径。union(x,y)合并 x、y 所在集合按秩 / 按大小合并防止树退化成链。基础模板int fa[N],sz[N]; int find(int x){ if(fa[x]!x) fa[x]find(fa[x]); //路径压缩 return fa[x]; } void unite(int x,int y){ xfind(x),yfind(y); if(xy) return; if(sz[x]sz[y]) swap(x,y); fa[x]y; sz[y]sz[x]; }初始化fa[i]isz[i]1每个点自己是一个集合。特性路径压缩 按秩合并单次操作接近 (O ( α ( n ) ) O(\alpha(n))O(α(n)))几乎常数。应用连通块统计、最小生成树 Kruskal、线段树分治可撤销并查集不能路径压缩只用按秩合并栈记录修改用于回滚。⚠可撤销回滚并查集禁止路径压缩只按秩合并把每一步修改压栈撤销时弹出恢复普通并查集不支持回滚。Dijkstra 算法作用求单源最短路图的边权必须全部 ≥0不能处理负权边。 思路起点距离置 0其余无穷大使用优先队列小根堆每次取出当前距离最小的点遍历该点所有邻边松弛更新邻点距离若更新成功入堆同一个点可能多次入堆旧的无效记录直接跳过。模板vectorpairint,int e[N]; //e[u] {v,w} int dis[N]; void dijkstra(int s){ memset(dis,0x3f,sizeof dis); dis[s]0; priority_queuepairint,int,vectorpairint,int,greater q; q.emplace(0,s); while(!q.empty()){ auto [d,u]q.top(); q.pop(); if(ddis[u]) continue; //旧的垃圾状态跳过 for(auto [v,w]:e[u]){ if(dis[v]dis[u]w){ dis[v]dis[u]w; q.emplace(dis[v],v); } } } }复杂度(O ( m log ⁡ n ) O(m\log n)O(mlogn))n点数m边数。注意边权负数不能用 Dijkstra换 SPFA/Bellman‑Ford。拓展多源最短路可以把多个起点初始距离设 0 全部扔进堆。二者简单对比并查集侧重连通关系不管边的权值大小适合合并集合、判断连通不适合求路径长度。Dijkstra侧重最短路径距离处理带权图求从起点到各点最小代价。组合场景Kruskal 最小生成树用 Dijkstra 求最短路用并查集判断两点是否连通依次加边。离散化什么时候用离散化场景数值本身范围巨大比如 (1 ∼ 10 9 ) 1\sim10^9)1∼109)但是真正用到的总个数很少只有( 2 × 10 5 ) (2\times10^5)(2×105))数组开不下 (10 9 10^9109) 大小但是我们只关心这些数字之间大小 / 相等关系不在乎它真实值多大。 把原始很大的数字映射成连续的小整数下标这个操作就是离散化。以程序自动分析举例 变量编号可以是1, 100, 999999999一共只出现最多 2n 个不同数字。 不需要开一千万数组只把这几十个 / 几万个数字映射成1,2,3,4…。离散化标准四步收集把所有要用到的原始数字全部放进 vectorvectorint num; num.push_back(a); num.push_back(b);排序sort(num.begin(), num.end());去重uniqueunique把数组里相邻重复元素挪到末尾返回去重之后的末尾迭代器。num.erase( unique(num.begin(),num.end()), num.end() );映射原始值 → 新编号用lower_bound二分查找返回第一个≥目标的位置。int id lower_bound(num.begin(),num.end(),val) - num.begin() 1;1可选让编号从 1 开始适配并查集习惯下标从 1。示例演示原始出现数字[100, 5, 999999999, 100]收集num [100,5,999999999,100]sort 排序num [5,100,100,999999999]unique 去重num [5,100,999999999]映射(5 → 1 5 \rightarrow 15→1)(100 → 2 100 \rightarrow 2100→2)(999999999 → 3 999999999 \rightarrow3999999999→3)以后 原始5就用1代表原始100用2原始999999999用3。 现在下标最大只有 3可以开数组 / 并查集。只保留相等关系原来相等的数映射后 id 一定相等原来不等映射后 id 不等。 ❗离散化只保留相对关系丢失真实数值大小。如果题目需要做加减、区间长度计算不能随便离散化。两种离散化区分普通离散化上面这种只关心元素是否相等。程序自动分析就是这一类。区间离散化线段树要保留区间间隔需要额外处理。程序自动分析里为什么必须离散化题目中 (i,j) 可以到 (10 9 10^9109)。 并查集fa[]数组不能开 (10 9 10^9109)。 但每组最多 n 条约束最多只有 2n 个不同的编号离散之后最多 2n 个 id数组开200010足够。代码片段vectorint num; //1.收集全部数字 for(int i1;in;i){ cinq[i].xq[i].yq[i].e; num.push_back(q[i].x); num.push_back(q[i].y); } //2排序 sort(num.begin(),num.end()); //3去重 num.erase(unique(num.begin(),num.end()),num.end()); //4 获取映射id auto get[](int v){ return lower_bound(num.begin(),num.end(),v)-num.begin()1; }; int uget(q[i].x); int vget(q[i].y);常见坑❗必须把本组所有用到的值全部先收集再排序去重。不能读一个离散一个。lower_bound数组必须提前排好序不然结果错误。多组测试每组 vector 要清空。如果题目需要计算差值如 (r‑l)不能直接离散。一句话总结离散化数据值范围极大但有效数据点数量少把原始值收集、排序、去重二分映射成连续小下标节约数组空间只保留相等 / 相对关系。P3367 【模板】并查集题意总结有 N 个元素M 次操作。1 X Y把 X、Y 两个元素所在集合合并。2 X Y查询 X、Y 是否属于同一个集合同一集合输出Y否则输出N。数据规模(N ≤ 2 × 10 5 M ≤ 10 6 N\le 2\times10^5M\le10^6N≤2×105M≤106)需要路径压缩建议加上按秩合并保证速度。解题思路并查集数组fa[]fa[x]代表 x 的父亲初始每个元素自己是自己的父节点fa[i]i。find 函数带路径压缩找 x 的根递归 / 迭代把路径上所有点直接指向根。合并 union找到 x、y 的根如果根不一样把其中一个根接到另一个根下面。处理操作Z1合并 X,YZ2判断find(X)find(Y)相等输出 Y否则 N。#includebits/stdc.h using namespace std; int fu[200005]; int find(int u){ if(ufu[u])return u; return fu[u]find(fu[u]); } int main(){ int n,m; cinnm; for(int i1;in;i)fu[i]i; for(int i0;im;i){ int z,x,y; cinzxy; if(z1){ xfind(x); yfind(y); if(xy)continue; fu[x]y; } else{ xfind(x); yfind(y); if(xy)coutYendl; else coutNendl; } } return 0; }P1955 [NOI2015] 程序自动分析(离散化并查集)题意概括多组测试每组给出 n 条约束(e1)(x i x j x_i x_jxi​xj​)(e0)(x i ≠ x j x_i \neq x_jxi​xj​)判断是否存在一组变量赋值使得全部约束同时成立输出YES/NO。关键点变量下标 (i,j) 最大可达 (10^9)无法直接开数组但一共只有最多 2n 个不同下标需要离散化。相等关系具备传递性不等没有传递性。解题思路离散化把本组所有出现过的 (i,j) 全部收集排序、去重用二分把巨大原始编号映射为连续小下标。并查集初始化。优先处理所有相等约束 e1把两个变量编号合并到同一个集合。相等有传递性(a b , b c ⇒ a c ab,bc \Rightarrow acab,bc⇒ac)。再校验全部不等约束 e0如果某条 (e0) 的两个变量已经在同一个集合说明推导出来它们必须相等又要求不等发生矛盾 → 答案NO。全部不等约束检查无冲突输出YES。⚠重要顺序先全部合并相等再检查不等不等条件不能做合并操作只做判断。#includebits/stdc.h using namespace std; const int N 200010; int fa[N]; struct Node{ int x,y,e; }q[N]; int find(int x){ if(fa[x]!x) fa[x]find(fa[x]); return fa[x]; } void unite(int x,int y){ xfind(x); yfind(y); if(x!y) fa[y]x; } void solve(){ int n; cinn; vectorint num; for(int i1;in;i){ cinq[i].xq[i].yq[i].e; num.push_back(q[i].x); num.push_back(q[i].y); } //离散化 sort(num.begin(),num.end());//排序 num.erase(unique(num.begin(),num.end()),num.end());//去重 auto getid[](int v){ return lower_bound(num.begin(),num.end(),v)-num.begin()1; }; int sznum.size(); for(int i1;isz;i) fa[i]i; for(int i1;in;i){ if(q[i].e1){ int ugetid(q[i].x); int vgetid(q[i].y); unite(u,v); } } bool oktrue; for(int i1;in;i){ if(q[i].e0){ int ugetid(q[i].x); int vgetid(q[i].y); if(find(u)find(v)){ coutNOendl; return; } } } coutYES\n; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int t; cint; while(t--) solve(); return 0; }P4779【模板】单源最短路径标准版Dijkstra题意给定n 个点、m 条带非负权的有向边从起点s出发求起点到每一个点的最短路径长度按编号顺序输出距离。数据规模大(n ≤ 10 5 m ≤ 2 × 10 5 n\le10^5m\le2\times10^5n≤105m≤2×105)边权可以很大距离会爆 int保证起点可以到达全部点没有不可达点必须用堆优化 DijkstraSPFA 会被卡超时。输入n m s之后 m 行 u v w表示 u→v边权 w。输出n 个数依次是 s 到 1~n 的最短路。解题思路算法选择图所有边权≥0选用堆优化 Dijkstra。朴素 Dijkstra (O ( n 2 ) O(n^2)O(n2))本题 n 最大(10 5 10^5105)会超时堆优化复杂度 (O ( m log ⁡ n ) O(m\log n)O(mlogn))可以通过大数据。建图使用邻接表存储有向图g[u]保存从 u 出发的所有终点 v边权 w。距离数组开long long类型dis[]初始为极大值 INF起点s距离置 0。小根堆优先队列存(当前距离,节点编号)初始把起点(0,s)入堆。小根堆每次自动取出距离最小的点。处理堆弹出堆顶距离最小的点 u如果 u 已经访问过直接跳过堆中存在旧的无效记录。标记 u 为已访问。遍历 u 的所有邻接边u→v权w尝试松弛如果dis[v] dis[u]w更新 v 的最短路把新的(dis[v],v)压入堆。输出按 1~n 顺序输出每个点的最短距离。核心堆帮我们省去每次遍历找全局最小距离点的 O (n) 循环vis 数组用来避免重复处理同一个点。注意边权总和很大距离必须用 long long防止整数溢出。关键逻辑非负权图一旦点从堆弹出被 vis 标记它的最短距离就已经确定之后不用再更新。堆里允许存放同一个点多条不同距离记录旧记录直接丢弃即可。#includebits/stdc.h using namespace std; const int INF 2147483647; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,m,s; cin n m s; vectorvectorpairint,int g(n1); //邻接表 g[u] {v,w} for(int i1;im;i){ int u,v,w; cin u v w; g[u].emplace_back(v,w); } vectorint dis(n1, INF); vectorbool vis(n1, false); dis[s] 0; // 小根堆 pair距离,节点 priority_queuepairint,int, vectorpairint,int, greaterpairint,int q; q.emplace(0, s); while(!q.empty()){ auto [d, u] q.top(); q.pop(); if(vis[u]) continue; vis[u] true; for(auto [v,w] : g[u]){ if(dis[u] ! INF (ll)dis[v] (ll)dis[u] w){ dis[v] dis[u] w; q.emplace(dis[v], v); } } } for(int i1;in;i){ cout dis[i]; if(i n) cout ; } cout endl; return 0; }