并查集示例

并查集 =“合并（Union）+ 查找（Find）”的集合，也叫Disjoint Set Union（DSU）。

它只做两件极快的事：

1. Find(x)– 问“x 在哪个集合？”→ 返回根节点
2. Union(x, y)– 把 x 所在集合与 y 所在集合合并成一个大集合

复杂度：
经过“路径压缩 + 按秩/大小合并”，单次操作平均O(α(n))，α 是反阿克曼函数，比 log n 还慢，但常数 < 5，可当作常数时间。

经典场景是任何需要“不断把元素合并、不断问是否同组”的问题。一句话，并查集就是“专门高效处理动态分组与连通查询”的最简数据结构。

例题

有若干个category：(1, 2), (2, 3), (4, 3), (5, 6), (6, 7, 10, 11)。
程序处理后需要输出这样的结果：(1, 2, 3, 4)，(5, 6, 7, 10, 11)。

importjava.util.*;publicclassMergeCategories{publicstaticvoidmain(String[]args){List<List<Integer>>input=Arrays.asList(Arrays.asList(1,2),Arrays.asList(2,3),Arrays.asList(4,3),Arrays.asList(5,6),Arrays.asList(6,7,10,11));List<Set<Integer>>merged=merge(input);for(Set<Integer>group:merged){System.out.println(group);}}privatestaticList<Set<Integer>>merge(List<List<Integer>>input){UnionFinduf=newUnionFind();for(List<Integer>list:input){if(list.isEmpty()){continue;}intfirst=list.get(0);for(intele:list){uf.union(first,ele);}}// 按根分组Map<Integer,Set<Integer>>groups=newHashMap<>();for(intx:uf.parent.keySet()){introot=uf.find(x);groups.computeIfAbsent(root,k->newLinkedHashSet<>()).add(x);}returnnewArrayList<>(groups.values());}// 并查集staticclassUnionFind{Map<Integer,Integer>parent=newHashMap<>();// 递归intfind(intx){intp=parent.computeIfAbsent(x,k->k);if(p!=x){parent.put(x,find(p));p=parent.get(x);}returnp;}voidunion(intx,inty){introotX=find(x);introotY=find(y);if(rootX!=rootY){parent.put(rootX,rootY);}}}}