并查集

首先，并查集是树状结构
查：确定元素属于哪一个集合，看图

image.png
查的一般代码写法：
查的基本思路：如果是根节点，直接返回该节点的值，否则递归该函数，参数为该节点的父节点，就是去找父节点是什么，结合图，代表一层一层向上走

int find(int parent[], int i) {
        if (parent[i] == -1)//如果i的父节点是-1，就代表该节点是根节点
            return i;
        return find(parent, parent[i]);//如果不是根节点，就返回该节点的父节点的父节点，///不断向上递归，如图所示
    }

并：将两个子集合并为一个集合，看图

image.png

基本思路：
先找这两个节点所属于的根节点，判断这两个根节点是否，不相等，代表不是一个集合，需要进行合并，就将xset这个根节点，指向yset这个根节点，xset作为一颗子树，如图所示

void union(int parent[], int x, int y) {
        int xset = find(parent, x);//找x的根节点
        int yset = find(parent, y);
        if (xset != yset)//不相等，代表不是一个集合，需要进行合并，就将xset这个根节点，指向yset这个根节点，xset作为一颗子树，如图所示
            parent[xset] = yset;
    }

路径压缩

image.png

如上图所示，如果像查那样一层一层的找父节点，最后的目的是确定根节点，但是如果树很高，这样找的话就太慢了，我们直接将所有节点都接到根节点，这样一步到位，效率很高啊
其实只改一行，改最后的返回值，如果不是根节点，不返回上一层节点，直接返回根节点

int find(int x) {
  if (x != fa[x])  // x不是自身的父亲，即x不是该集合的代表
    fa[x] = find(fa[x]);  // 查找x的祖先直到找到代表,于是顺手路径压缩
  return fa[x];
}

举例，例如之前做的朋友圈那个题

image.png

parent[i]存的是i节点的父节点

public class Solution {
    int find(int parent[], int i) {
        if (parent[i] == -1)//如果一个节点的父节点是-1，就代表该节点是该树的根节点
            return i;
        return find(parent, parent[i]);
    }

    void union(int parent[], int x, int y) {
        int xset = find(parent, x);
        int yset = find(parent, y);
        if (xset != yset)
            parent[xset] = yset;
    }
    public int findCircleNum(int[][] M) {
        int[] parent = new int[M.length];
        Arrays.fill(parent, -1);//初始化都为独立的根节点，为-1
        for (int i = 0; i < M.length; i++) {
            for (int j = 0; j < M.length; j++) {//遍历矩阵
                if (M[i][j] == 1 && i != j) {//如果其中两个节点相连，就合并这两个子集
                    union(parent, i, j);
                }
            }
        }
        int count = 0;
        for (int i = 0; i < parent.length; i++) {//遍历parent数组，出现-1
//就代表是根节点，就代表是一个连通分量
            if (parent[i] == -1)
                count++;
        }
        return count;
    }
}