并查集

基本描述

并查集用于分类，快速将一堆元素根据相对关系分成几个子集。对于一个新的元素，可以快速判断其属于哪个子集。注意这里是相对关系，这说明对于一个元素属于哪个子集的判断无法通过一个固定的规则进行。比如，判断元素是否是基数就是一个固定的规则，不需要使用并查集。但如果是把这些元素中连续的放在一起，则就可以使用并查集来操作。

适用范围

给定一个集合，要求按照其中元素间的关系把它们分成几个子集，这种场景需要使用并查集。

算法原理

由于元素间的关系是相对的，则这种关系存在传递性，即如果a和b相关，且b和c相关，则a，b，c都是相关的，可以分为一个子集。自然想到树状结构。那么先设定初始状态，后续递归的去做关联，最后就可以得到多棵树，每一棵树都是一个子集。

具体来说，需要维护的就是元素本身和其父节点的关系。初始设定元素自己就是自己的父节点。后续递归的寻找，如果其父节点不是自己，则其父节点应该是父节点的父节点。

实现方法

并查集可以用map来维护节点和其父节点的关系，如果元素个数和值有限，则用数组维护也可以。并且提供find和union两个方法，find方法用于找到和维护元素的父节点，union方法用于合并两个子集。

class UnionFind{
  private HashMap<Integer,Integer> map;
  public UnionFind(int[] nums){
    map = new HashMap<>();
    for(int i: nums){
    //初始化，每个元素的父节点都是自己
      map.put(i,i);
    }
  }
  public Integer find(int x){
    if (!map.containsKey(x)) {
        return null;
    }
    if(map.get(x) == x){
      return x;
    }else{
      int p = find(map.get(x));
      map.put(x,p);
      return p;
    }
  }
  public void union(int x, int y){
    int rx = find(x);
    int ry = find(y);
    if(rx==ry) return;
    map.put(rx,ry);
  }
}

应用

使用的时候一般是如下模式：

遍历集合，如果当前元素的相关元素用find方法找到了，则再用union方法将当前元素和它相关的元素做union。结束后并查集构建完毕，再根据具体需求去使用即可。

举例：

找到数组中最多的相邻元素个数

class Solution {
    public int longestConsecutive(int[] nums) {
        UnionFind uf = new UnionFind(nums);
        int ans = 0;
        
        for (int num : nums) {
            // 当num+1存在，将num合并到num+1所在集合中(相关元素)
            if (uf.find(num + 1) != null) {
                uf.union(num, num + 1);
            }
        }
        for(Integer x: uf.map.keySet()){
            System.out.println(x+"_"+uf.map.get(x));
        }
        for (int num : nums) {
            // 找到num的最远连续右边界
            int right = uf.find(num);
            ans = Math.max(ans, right - num + 1);
        }
        return ans;
    }
}