并查集

• 概念
• 核心思路：
• 代码模板
• 相关题目

[toc]

概念#

• 谁和谁相互关联， 问你最终每个集体或者最多集体有多少人， 或者有多少个集体，用并查集即可。

• 区间合并问题直接上并查集，别整更新左区间，更新右区间这种玩意，很容易错。

核心思路：#

1. partent[k] 指k的父亲节点是什么
2. 每次getParent(k)时， 要通过递归， 将其父节点更新成最上面的父节点，实现并查集的压缩，大大减少了复杂度
3. union时， 则随意选一方进行连接
4. 如何涉及集合中的数量问题，尽量别在union中更新，容易写错， 建议最后全部遍历一边，得到集合中的数量或者价值总数。
5. 如果一定要union更新，注意顺序，p[p1]] = p2的话，说明p1的父亲变成了p2，那么应该是p2作为被加方，即sum[p2] += sum[p1]，反过来了。且注意在getParent中不需要更新val

代码模板#

   long[] sums;
   int[] parent;    

void union(int n1, int n2) {
       int p1 = getParent(n1);
       int p2 = getParent(n2);
       parent[p1] = p2;
       sums[p2] += sums[p1];
   }

   int getParent(int num) {
       int p = parent[num];
       if (p == num) {
           return p;
       } else {
           p = getParent(p);
       }
       parent[num] = p;
       return p;
   }

相关题目#

6159. 删除操作后的最大子段和 - 力扣（LeetCode）