并查集维护一组互不相交的集合，核心操作只有查找代表元 find 和合并 union。每个元素最初自成集合，parent[x]=x；若两个元素代表元相同，它们已经连通，否则把一棵代表树接到另一棵上。

朴素合并可能形成很长的链。按秩或按大小合并总让较小树接到较大树，控制高度；路径压缩在查找时把沿途节点直接指向根，使后续查询更快。

1
2
3
4
5
6
7
find(x):
  if parent[x] != x:
    parent[x] = find(parent[x])
  return parent[x]
union(a,b):
  ra=find(a); rb=find(b)
  if ra != rb: attach smaller to larger

同时采用两种优化后，连续 m 次操作的均摊复杂度为 O(m α(n))，反阿克曼函数增长极慢，实践中接近常数；空间为 O(n)。并查集适合无向图连通性、冗余边、岛屿动态合并和 Kruskal 最小生成树。

它擅长合并，却不擅长删除边和回答两点具体路径。若问题要求有向可达、最短路径或集合拆分，需要其他结构。离线问题有时可倒序把删除转化为添加；带权并查集还能维护节点到根的关系，但不变量更复杂。

常见误区是合并 a 与 b 本身而非其根、路径压缩后忘记返回新根、秩更新条件错误、把无向连通用于有向路径，以及声称严格 O(1)。小结：代表元提供集合身份，按大小合并限制树高，路径压缩让历史查询为未来查询铺平道路。