并查集 Union-Find
数据结构 · 极快地维护「谁和谁同组」
什么是并查集
前面的结构大多在存「数据序列」；并查集（Union-Find，又叫不相交集合 DSU）换了个差事——把一堆元素分成若干不相交的组，专门极快地回答两件事：find(x) 这个元素属于哪个组（返回组的代表元、也就是「根」）、union(a,b) 把两个组合并成一个。
实现很巧：每个元素记一个 parent，顺着 parent 一直走到「自己指自己」的那个就是根。同根 = 同组；合并，就是把一个根指到另一个根上。这里有 8 个元素，一开始各自成组。选两个元素点「合并」，或「查根 / 连通?」试试。
亲手试试
当前 8 个组（连通分量）
选两个元素「合并」，或「查根 / 连通?」试试。一开始 8 个元素各自成组。
朴素的 find 可能要顺着一条长链一路走到根。路径压缩是点睛之笔：find 找到根之后，把沿途每个节点直接指向根，下次再 find 几乎一步到位——并查集能做到近乎 O(1)，就靠路径压缩（外加按秩合并）。连成一条链后点「查根」，看箭头怎么齐刷刷改指向根。
并查集在哪里用
连通性判断：朋友圈 / 网络节点是否连通，一个 connected 搞定。
Kruskal 最小生成树：加一条边前，用它判断两端是否已连通（会不会成环）。
岛屿 / 连通分量计数：合并相邻同类，最后数有几个组。
账号合并 / 等价类：把判定为「同一个」的对象并到一起。
Kruskal 最小生成树：加一条边前，用它判断两端是否已连通（会不会成环）。
岛屿 / 连通分量计数：合并相邻同类，最后数有几个组。
账号合并 / 等价类：把判定为「同一个」的对象并到一起。
它不存序列、只管「同不同组」，是一种用途专一、实现精巧的结构。