# 并查集 ## 定义 并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。 并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。 ## 一张图快速入门 1. 先将普通节点初始化为并查集，每一个集合内都只有自己 2. 当2个节点要合并时，先判断是不是在同一个集合中，如果是则跳过，不是则合并 3. 合并的时候，先找到要合并节点的头节点，再将小数量集合的头节点指向大数量集合的头节点。 4. 在获取头节点的时候做偏平化处理，加快下次找头节点的过程  ## java实现并查集 [Java实现并查集](Java%E5%AE%9E%E7%8E%B0%E5%B9%B6%E6%9F%A5%E9%9B%86.md) ## 测试 ~~~ public static void main(String[] args) { List<String> list = new ArrayList<>(); list.add("A"); list.add("B"); list.add("C"); list.add("D"); list.add("E"); UnionFindSet<String> unionFindSet = new UnionFindSet<>(list); unionFindSet.union("A","B"); unionFindSet.union("C","D"); System.out.println(unionFindSet); unionFindSet.union("E","B"); System.out.println(unionFindSet); unionFindSet.union("C","E"); System.out.println(unionFindSet); } ~~~ 输出：（和上图例子步骤保持一致） ``` UnionFindSet{dataMap={A=Node{val=A, pre.val=A}, B=Node{val=B, pre.val=A}, C=Node{val=C, pre.val=C}, D=Node{val=D, pre.val=C}, E=Node{val=E, pre.val=E}}, countMap={Node{val=E, pre.val=E}=1, Node{val=A, pre.val=A}=2, Node{val=C, pre.val=C}=2}} UnionFindSet{dataMap={A=Node{val=A, pre.val=A}, B=Node{val=B, pre.val=A}, C=Node{val=C, pre.val=C}, D=Node{val=D, pre.val=C}, E=Node{val=E, pre.val=A}}, countMap={Node{val=A, pre.val=A}=3, Node{val=C, pre.val=C}=2}} UnionFindSet{dataMap={A=Node{val=A, pre.val=A}, B=Node{val=B, pre.val=A}, C=Node{val=C, pre.val=A}, D=Node{val=D, pre.val=C}, E=Node{val=E, pre.val=A}}, countMap={Node{val=A, pre.val=A}=5}} ```