并查集
入门并查集最擅长回答"这两个点现在是不是一组"。
// 算法讲解
并查集
示例会合并两组元素，再查看 find 如何把路径压缩到代表元。
待机
速度 中
待机 ⌨1vector<int> parent, sz;
2
3int findSet(int x) {
4 if (parent[x] == x) return x;
5 return parent[x] = findSet(parent[x]);
6}
7
8void unionSet(int a, int b) {
9 a = findSet(a);
10 b = findSet(b);
11 if (a == b) return;
12 if (sz[a] < sz[b]) swap(a, b);
13 parent[b] = a;
14 sz[a] += sz[b];
15}
复杂度分析
时间 均摊近似 O(1)
空间 O(n)
最优 O(1)
最坏 O(alpha(n))
算法讲解
并查集用 parent 数组维护每个节点所属集合的代表元，find 查根，union 合并集合。
路径压缩和按秩合并是两个核心优化，它们能把均摊复杂度压到几乎常数级。
Kruskal 最小生成树、动态连通性、朋友圈合并等问题都会反复使用它。
学习它时要特别理解"树只是表示方式，真正关心的是集合归属关系"。