①核心要点与万能模板
| 知识板块 | 必须记住的核心 | 复杂度 |
|---|
| 森林表示 | 集合 = 一棵树，根 = 代表元，parent[x]==x | 空间 O(n) |
| find | 沿 parent 上溯到自指节点，递归版一行搞定 | O(α(n)) |
| union | 先求两根，同根返回 false，异根挂接 | O(α(n)) |
| 路径压缩 | parent[x] = find(parent[x]) | 均摊 O(log n) |
| 按秩/按大小合并 | 小树挂大树，sz[ra] += sz[rb] | 树高 O(log n) |
| 两者结合 | 工程上等价于 O(1)，α(n) ≤ 4 | O(m·α(n)) |
| 连通块计数 | 初值 n，每次成功合并 −1；或统计根个数 | O(1) / O(n) |
| 带权并查集 | 压缩时 d[x] += d[parent[x]]；合并 d[ry]=d[x]+w−d[y] | O(α(n)) |
| 可撤销并查集 | 不压缩 + 按秩合并 + 栈记录改动的三要素 | O(log n) |
C++万能模板 · 普通并查集（背下来）
const int MAXN = 100005;
int parent[MAXN], sz[MAXN];
void init(int n) {
for (int i = 1; i <= n; i++) { parent[i] = i; sz[i] = 1; }
}
int find(int x) { // 路径压缩
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
bool unite(int a, int b) { // 按大小合并
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (sz[ra] < sz[rb]) swap(ra, rb);
parent[rb] = ra;
sz[ra] += sz[rb];
return true;
}
bool same(int a, int b) { return find(a) == find(b); }
🔍 代码逐段解析 · 普通并查集模板
init —— parent 与 sz 必须同时初始化；只初始化 parent，第一次按大小合并会拿 sz=0 做比较，等于随机挂接。
find —— 一行版：parent[x]==x ? x : parent[x]=find(parent[x])，递归出口与路径压缩合二为一，考场默写最优形式。
unite —— 返回 bool 是刻意的：调用方靠它判断「这次是否真的合并了」，连通块计数、Kruskal 选边都依赖这个返回值。
same —— 千万别写成 parent[a]==parent[b]（比爹不比根）。
易错点 —— 多组数据忘 init；swap 后写反挂接方向（把大树挂到小树下）。
C++万能模板 · 带权并查集（背下来）
int parent[MAXN];
long long d[MAXN]; // 到父亲的权值
void init(int n) {
for (int i = 1; i <= n; i++) { parent[i] = i; d[i] = 0; }
}
int find(int x) {
if (parent[x] == x) return x;
int root = find(parent[x]);
d[x] += d[parent[x]]; // ★ 压缩必须同步累加
return parent[x] = root;
}
// 已知 y 相对 x 的权值为 w，合并且使约束成立
void unite(int x, int y, long long w) {
int rx = find(x), ry = find(y);
if (rx == ry) return; // 同根时用 d[x]-d[y] 校验
parent[ry] = rx;
d[ry] = d[x] + w - d[y]; // ★ 关键合并公式
}
🔍 代码逐段解析 · 带权并查集模板
find 三步曲 —— ①root = find(parent[x]) 先让父节点压到根；②d[x] += d[parent[x]] 把「x→父」加上「父→根」；③return parent[x] = root 改挂根。顺序错一步，全盘皆输。
unite 参数 w —— 语义是「y 相对 x 的权值」：公式 d[ry] = d[x] + w − d[y] 由向量关系 d[y]+d[ry] = d[x]+w 解出，用前先画 30 秒向量图确认方向。
同根时 —— unite 直接 return，调用方应改用 d[x]−d[y] 做校验（矛盾检测），见排座位 / 食物链。
易错点 —— ①d 数组类型：距离型用 long long，关系型（模 k）用 int；②压缩时先改 parent 再累加 d。
②拓展案例
拓1银河英雄传说（带权并查集经典）
题意简述：初始有 30000 艘战舰，每艘单独成一列。两种指令：M i j 把 i 所在整列接到 j 所在列之后；C i j 询问 i、j 之间隔了多少艘战舰（同列时），不同列输出 −1。
思路：这是带权并查集的「样板题」。
维护两个量：d[x] = x 到所在列队头的距离（即前面有几艘船）；sz[root] = 该列总长度。
合并 M i j：把 i 的队头接到 j 的队尾之后。d[ri] = sz[rj]（i 原来前面有 sz[rj] 艘），sz[rj] += sz[ri]。
查询 C i j：同根时答案 = |d[i] − d[j]| − 1（中间间隔的船数 = 距离差再减 1）。
与普通并查集的差别：合并时 i 的整列必须"整体平移"，靠 d 数组在路径压缩时累加实现，等价于 O(1) 平移整列。这正是带权并查集巧妙的地方。
C++银河英雄传说 — 核心代码
const int N = 30005;
int parent[N], sz[N], d[N]; // d[x]: x 前面有几艘船
int find(int x) {
if (parent[x] == x) return x;
int root = find(parent[x]);
d[x] += d[parent[x]]; // 累加到队头的距离
return parent[x] = root;
}
void merge(int i, int j) { // 把 i 列接到 j 列后面
int ri = find(i), rj = find(j);
if (ri == rj) return;
parent[ri] = rj;
d[ri] = sz[rj]; // i 列整体排在 j 列之后
sz[rj] += sz[ri];
}
int query(int i, int j) {
if (find(i) != find(j)) return -1;
return abs(d[i] - d[j]) - 1;
}
运行结果
输入: 4
M 2 3
C 1 2
M 2 4
C 4 2
输出: -1
1
说明: 第 2 行时 1 与 2 不同列 → -1；
第 3 行后顺序为 [4,3,2]（2 所在列整体接到 4 之后），
4 与 2 之间隔 1 艘船 → 1。
拓2程序自动分析（离散化 + 并查集） NOI2015
题意简述：给出 n 个形如 x = y 或 x ≠ y 的约束，问是否存在一组赋值使所有约束同时成立。x、y 的取值可达 109。
思路（两阶段贪心）：
阶段一：把所有 x = y 的约束用并查集合并（相等具有传递性，可以随便合）。
阶段二：再检查所有 x ≠ y 的约束。若发现某个约束的两端 find(x) == find(y)，说明「又有 x=y 又有 x≠y」，矛盾，输出 NO；全部通过则 YES。
关键技巧：x、y 高达 109，但实际出现的不同取值不超过 2n 个，所以先离散化映射到 1..2n，再用大小为 2n 的并查集。
正确性直觉：「相等」是等价关系，可以随意合并；而「不等」会破坏等价类，必须最后检查——先合后验的顺序不可颠倒。
C++程序自动分析 — 完整代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int parent[MAXN];
struct Node { int x, y, e; } a[MAXN];
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
int main() {
ios::sync_with_stdio(0);
int T; cin >> T;
while (T--) {
int n; cin >> n;
vector<int> v;
for (int i = 0; i < n; i++) {
cin >> a[i].x >> a[i].y >> a[i].e;
v.push_back(a[i].x); v.push_back(a[i].y);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end()); // 离散化
int m = v.size();
for (int i = 1; i <= m; i++) parent[i] = i;
auto id = [&](int val) {
return lower_bound(v.begin(), v.end(), val) - v.begin() + 1;
};
// 阶段一：先处理所有「相等」
for (int i = 0; i < n; i++)
if (a[i].e == 1) parent[find(id(a[i].x))] = find(id(a[i].y));
// 阶段二：再校验所有「不等」
bool ok = true;
for (int i = 0; i < n && ok; i++)
if (a[i].e == 0 && find(id(a[i].x)) == find(id(a[i].y))) ok = false;
cout << (ok ? "YES" : "NO") << '\n';
}
return 0;
}
运行结果
输入: 2
2
1 2 1
1 2 0
2
1 2 1
2 3 1
输出: NO
YES
说明: 第一组同时要求 1=2 且 1≠2，矛盾。
第二组只有相等约束，显然可行。
🔍 代码逐段解析 · 程序自动分析
结构体数组（第 6~7 行） —— 把 n 条约束先整体存下（x, y, e，e=1 相等 / e=0 不等），因为必须先合并完所有相等、再检查所有不等，不能边读边做。
离散化（第 16~22 行） —— 取值高达 109 但最多 2n 个不同值：排序 + unique 去重，lambda id(val) 用 lower_bound 把原值映射到 1..m。
阶段一（第 25~26 行） —— 只处理 e==1：parent[find(id(x))] = find(id(y)) 直接把两根相连。相等是等价关系，先合不亏。
阶段二（第 28~30 行） —— 逐条检查 e==0，两端同根即矛盾，置 ok=false 并用 && ok 提前结束循环。
易错点 —— ①顺序颠倒：先检查不等再合并相等，会把本可满足的数据判成 NO；②离散化数组只开 n 不够（最多 2n 个不同值）。
拓3最小生成树 Kruskal（并查集的最大舞台）
题意简述：给定 n 个点 m 条带权无向边，求连通所有点的最小总权值和（最小生成树）。
思路（Kruskal 算法）：把所有边按权值从小到大排序，依次考察每条边：用并查集判断它的两个端点是否已经连通——不连通就选它并合并，已连通就跳过（选它会成环）。选满 n−1 条边即得最小生成树。
正确性直觉（反证）：假设最优解不含当前这条最小可用边 e，那么把 e 加入最优解必然成环；环上必有一条不短于 e 的边（因为 e 是连通两侧的最小边），删掉它得到不更差且含 e 的解——矛盾。
复杂度：排序 O(m log m) + 并查集 O(m·α(n))，是稀疏图上最快的 MST 算法，也是并查集最经典的应用。
C++Kruskal — 完整代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005, MAXM = 200005;
struct Edge { int u, v, w; } e[MAXM];
int parent[MAXN], sz[MAXN];
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
int main() {
ios::sync_with_stdio(0);
int n, m; cin >> n >> m;
for (int i = 0; i < m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
sort(e, e + m, [](const Edge &a, const Edge &b) { return a.w < b.w; });
for (int i = 1; i <= n; i++) { parent[i] = i; sz[i] = 1; }
long long sum = 0; int pick = 0;
for (int i = 0; i < m && pick < n - 1; i++) {
int ru = find(e[i].u), rv = find(e[i].v);
if (ru == rv) continue; // 成环，跳过
if (sz[ru] < sz[rv]) swap(ru, rv);
parent[rv] = ru; sz[ru] += sz[rv];
sum += e[i].w; pick++;
}
if (pick < n - 1) cout << "orz" << '\n'; // 图不连通
else cout << sum << '\n';
return 0;
}
运行结果
输入: 4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出: 7
说明: 选 (1,2)=2、(1,3)=2、(1,4)=3，共 7，
三条边把 4 个点连通，即为最小生成树。
🔍 代码逐段解析 · Kruskal 最小生成树
排序（第 14 行） —— lambda 按 a.w < b.w 升序；这是贪心的前提：每次都考虑当前最便宜的边。
init（第 15 行） —— parent 与 sz 同时初始化，注意在排序之后做也一样，但必须在合并循环之前。
合并循环（第 17~23 行） —— pick < n-1 是提前剪枝：选满 n−1 条即可停。两端同根 continue（选了成环）；异根则小挂大、sum += e[i].w、pick++。
判不连通（第 24~25 行） —— 循环结束 pick 仍 < n−1，说明图不连通，按洛谷 P3366 惯例输出 orz。
易错点 —— ①sum 不开 long long：m 条边权各 105 级别时总和会爆 int；②把判环写在合并之后（永远同根）。