---

第一类：基础连通性（“连不连”）

核心特征：只维护节点之间**“是否在同一集合”**，不关心具体距离或复杂关系。

应用场景	具体描述	代表题目/算法
无向图动态连通性	不断加边，询问两点是否连通，或询问连通块个数。	洛谷 P1551 亲戚、Kruskal 最小生成树（判环）
冗余连接（环检测）	加边时如果两点已在同一集合，则这条边是多余的（构成环）。	LeetCode 684 冗余连接
社交网络（好友关系）	判断两人是否在同一个朋友圈（传递性：朋友的朋友是朋友）。	基础入门题
静态离线连通（Tarjan LCA）	Tarjan 算法求最近公共祖先时，利用并查集离线标记回溯路径。	Tarjan-LCA 算法

---

第二类：等价关系与约束满足（“是不是同类 / 等不等”）

核心特征：题目只告诉你“A与B相等”或“A与B不等”，具有传递性（相等），但不具有传递性（不等）需特殊处理。

应用场景	具体描述	代表题目
变量相等/不等约束判定	先合并所有“相等”关系，再检查所有“不等”是否冲突。	程序自动分析
离散化+并查集	值域极大（1e9）但个数极少（1e5），先离散化再维护等价类。	程序自动分析（离散化配合）

---

第三类：边带权并查集（“差多少 / 谁吃谁 / 奇偶性”）

核心特征：维护节点到父节点（或根）的数值关系，关系通过加减法或模运算叠加。

应用场景	具体描述	权值含义	代表题目
线性距离（相对位置）	队列合并，询问两艘战舰中间隔了多少艘。	d[x]：到父节点的距离（整数加减）。	银河英雄传说（P1196）
环形关系（模 K 加法）	三类动物循环捕食（A吃B，B吃C，C吃A）。	d[x]：0同类，1吃根，2被根吃（模3）。	食物链（P2024）
奇偶性判定（异或关系）	区间内 1 的个数是奇数还是偶数。	d[x]：0相同，1不同（异或叠加）。	Parity Game（AcWing 239）
偏序关系（大于/小于）	维护元素之间的大小比较（如差值固定）。	d[x]：到根的差值。	带权值的并查集变种题

口诀：只要关系能转化为“数字偏移”，就用边带权。

---

第四类：扩展域并查集（“多状态逻辑拆点”）

核心特征：把每个元素拆成多个“分身节点”（如奇数域/偶数域，或 A/B/C 身份），把“逻辑推导”变成“集合连通”。

应用场景	具体描述	拆点方式	代表题目
奇偶性逻辑（2种状态）	判断 sum[x] 是奇数还是偶数的命题是否冲突。	拆成 x_odd 和 x_even（开2倍空间）。	Parity Game（扩展域写法）
三类身份逻辑（3种状态）	每个动物可能是 A/B/C，且关系复杂（同类/吃）。	拆成 x_self、x_eat、x_enemy（开3倍空间）。	食物链（扩展域写法）
二分图判定（2-SAT简化）	判断“敌对关系”（敌人的敌人是朋友）。	拆成 x 和 x+n（分别代表黑/白或真/假）。	关押罪犯（扩展域思想）

口诀：状态种类极少（2或3种）且关系是“逻辑互推”时，用扩展域比边带权更直观、不容易写错公式。

---

第五类：贪心 + 并查集“前驱指针”（“找空位 / 占座”）

核心特征：用于处理**“从当前位置往前数第一个空闲位置”的问题。合并时不是连“逻辑关系”，而是把被占用的位置指向它的前一个位置**。

应用场景	具体描述	代表题目
任务调度/商品售卖	每个商品有利润和过期日，一天只能卖一件，求最大利润。	并查集维护“最近空闲日期”（POJ 1456 / 超市）
区间染色 / 覆盖	每次把一段区间涂色，询问未被涂色的点（通过跳转跳过已涂色块）。	区间覆盖变种题
拼图 / 占位	类似并查集的“下一个空位”优化（DSU on a line）。	数据结构优化题

---

第六类：离线逆向并查集（“时光倒流”）

核心特征：题目涉及**“删除点 / 删除边”，但并查集不支持删除。于是反过来**，从最终状态开始，把删除当成添加，倒着处理。

应用场景	具体描述	代表题目
图遭到破坏后的连通性	不断删除一些边或节点，询问某时刻两点是否连通。	洛谷 P1197 [JSOI2008] 星球大战
洪水淹没 / 水位变化	随时间推移，部分点失效，问连通块变化情况。	并查集离线倒序经典题

---

第七类：维护集合附加信息（不只是连通）

核心特征：除了维护根，还额外维护集合的大小（size）、最大值、最小值、特定标记等。

应用场景	具体描述	代表题目
连通块大小/元素个数	合并时统计每个集合有多少个节点（常见于按秩合并的 size 数组）。	几乎所有并查集题目的辅助
集合内是否有特定元素	如合并时用按位或（`	`）记录该集合是否包含质数、偶数等。
动态维护最大值/最小值	合并时根节点保留集合内最大或最小值。	特殊变种题

---

终极统计 & 选择口诀（帮你快速对号入座）

拿到一道新题时，按下面顺序问自己：

1. 问关系是否带“权值”（距离、差值、奇偶、捕食）？

   • 是 → 边带权（模加法 / 异或 / 加减法）。
   • 否 → 进入下一步。

2. 问状态种类是否极少（2种或3种）且需要逻辑推导？

   • 是 → 扩展域（拆点，直接连通判断）。
   • 否 → 进入下一步。

3. 问是否涉及“查找前面第一个空位”（过期、占座）？

   • 是 → 前驱指针（fa[x] = find(x-1)）。
   • 否 → 进入下一步。

4. 问是否涉及删除操作（删边/删点）？

   • 是 → 离线倒序（逆向加边）。
   • 否 → 进入下一步。

5. 以上都不是，只问“连不连” → 普通并查集。

这张表基本涵盖了 NOI / NOIP / LeetCode 中 95% 以上的并查集考题。你一路从离散化问到食物链，已经把这七大类都摸过一遍了，接下来碰到新题，直接对照这张“兵器谱”找武器就行！😊