总结

  1. 初始化数组
  2. 合并 merge（普通合并 或者 按秩合并）
  3. 寻找根节点 find （完全压缩 或者 隔代压缩）

初始化数组
int[] parent;

// n (如果是0 ~ n）
// n + 1 (如果是1 ~ n)
public void init(int n) {
  
  // 自己本身就是父亲节点
  for(int i = 0; i < n; i++) {
    parent[i] = i;
  }
}
普通合并
public void init(int i, int j) {
  int x = parent[i];
  int y = parent[j];
  parent[y] = x;
}
寻找根节点
  • 隔代压缩
public int find(int index) {
  while(index != parent[index]) {
    parent[index] = parent[parent[index]];
    index = parent[index];
  }
  
  return index;
}
  • 完全压缩
public int find(int index) {
  if(index != parent[index]) {
    int father = find(parent[index]);
    index = father;
  }
  
  return parent[index];
}


典型题目

亲戚问题

参考：并查集

/**
 * @author SHshuo
 * @data 2022/3/12--17:29
 */
public class Third {

//    存储每个元素的父节点
    int[] fa = new int[5005];

//    存储每个根节点对应的树的深度
    int[] rank = new int[5005];

//    n个人、m个亲戚关系，询问p对亲戚关系，x、y表示互相为亲戚
    static int n, m, p, x, y;

    public static void main(String[] args) {
        Third third = new Third();
        third.init(n);
        for(int i = 0; i < m; i++){
            third.merge(x, y);
        }

        for(int i = 0; i < p; i++){
            System.out.println(third.find(x) == third.find(y) ? "YES" : "NO");
        }
    }

//    初始化、每个元素都是父节点
    public void init(int n){
        for(int i = 1; i <= n; i++){
            fa[i] = i;
            rank[i] = 1;
        }
    }

//    寻找父节点
    public int find(int x){
                //完全合并
        return x == fa[x] ? x : (fa[x] = find(fa[x]));
    }

//    根据根节点的深度进行合并
    public void merge(int i, int j){
        int x = find(i), y = find(j);

                //按秩合并
        if(rank[x] <= rank[y]){
            fa[x] = y;
        }else{
            fa[y] = x;
        }

        if(rank[x] == rank[y] && x != y){
            rank[y]++;
        }
    }

}

990. 等式方程的可满足性
class Solution {
    public boolean equationsPossible(String[] equations) {
        int[] parent = new int[26];
        // 初始化
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }

        // 如果是等号、合并
        for (String str : equations) {
            if (str.charAt(1) == '=') {
                int index1 = str.charAt(0) - 'a';
                int index2 = str.charAt(3) - 'a';
                union(parent, index1, index2);
            }
        }


        for (String str : equations) {
            if (str.charAt(1) == '!') {
                int index1 = str.charAt(0) - 'a';
                int index2 = str.charAt(3) - 'a';
                // 不在同一个集合中
                if (find(parent, index1) == find(parent, index2)) {
                    return false;
                }
            }
        }
        return true;
    }


    // 普通合并
    public void union(int[] parent, int index1, int index2) {
                int x = find(parent, index1);
                int y = find(parent, index2);
        parent[y] = x;
    }


    // 寻找父节点
    public int find(int[] parent, int index) {
        while (parent[index] != index) {
            // 路径压缩的隔代压缩
            parent[index] = parent[parent[index]];
            index = parent[index];
        }
        return index;
    }
}

补充

alt