并查集

目录

1.为什么学习并查集

2.并查集的概念

3.并查集代码的实现

4.并查集的题目

正文

1.为什么学习并查集

学习并查集主要是它在处理动态连通性和集合合并与查询问题时，有着极高的效率和简洁的实现。
具体来说有三大理由：
1.解决一类特定的问题：合并两个集合，以及查找一个元素属于哪一个集合。比如判断两个人是否在同一个朋友圈，或计算一个图中还有多少个连通区域。
2.性能极佳：加入“路径压缩”和“按秩合并”优化后，多次操作的平均时间复杂度近乎常数级别。
3.应用广泛且是算法基础。

2.并查集的概念

在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元元素集合，然后按一定的规律将属于同一元素的集合（元素）合并。在此过程中要反复用到查询某一个元素是否属于那个元素的运算。适合于描述这类问题的抽象数据类型称为并查集。

• 比如:某企业在某高校进行春招，已知软工专业的招了4人，计科招了3人，信安招了3人。共10人。该10来自不同的班级，起初互不认识。每个学生都是一个小的团体。现给这些学生进行编号：{0，1，2，3，4，5，6，7，8，9}；用以下数组来存储每个小集体，数组下标对应的数字代表：该小集体中所具有的成员数量。（符号代表是根元素）
  图：
  

• 进入公司后，这十个人需要分团队完成工作。经过一番讨论，程序猿A组为A={0，6，7，8},程序猿B组为B={1，4，9}，程序猿C组为C={2，3，5}，分成了不同的小组，于是他们组内成员经过自我介绍就认识了。只是组内认识哦，并不是10个人都认识了。在自我介绍的过程中，他们各个小组又选出了最适合的小组组长，A组长：0，B组长：1，C组长：2。于是形成了下面的小分队。
  

每个小分队视为一个朋友圈。

从上图可以看出：编号6，7，8的同学属于0号小分队，该小分队总共有4人（包含0号小组长）；编号4，9的同学属于1号小分队，该小分队有3人（包含小组长1）；编号为3，5的同学属于2号小分队，该小分队有3人（包含小组长2）。

观察上图有以下结论：
1.数组下标对应集合中的元素的编号（此处指：数组下标对应春招的10位员工的编号）。
2.数组中若为负数，负号是根的标志，该数是负数说明是根，数字则代表该集合中总的元素个数。
3.数组中若为非负数，代表该元素双亲在数组中的编号。
以编号9为例：
编号9的双亲是1，所以下标9中的数字是非负数1；接着，1下标的数字是负数-3，代表1是根节点，且以1为根的集合有3个元素。

• 不久，三个小组接到了一个大项目和一个小项目，经过商量决定，由A组与B组共同完成大项目，且该大项目的负责人为编号0；C组负责完成小项目。于是，他们的朋友圈又发生了变化，变成了以下的情况：
  
  这即为合并的概念。

3.并查集代码的实现

import java.util.Arrays;

public class UnionFindSet {
    public int[] elem;

    public UnionFindSet(int n) {
        this.elem = new int[n];
        Arrays.fill(elem,-1);
    }

    /**
     * 查找x下标的根
     * @param x
     * @return
     */
    public int findRoot(int x){
        if(x<0){
            throw new IndexOutOfBoundsException("下标不合法，是负数");
        }
        while(elem[x]>=0){
            x=elem[x];
        }
        return x;
    }

    /**
     * 判断x1  x2是否在同一个集合中
     * @param x1
     * @param x2
     * @return
     */
    public boolean isSameUnionFindSet(int x1,int x2){
        int index1=findRoot(x1);
        int index2=findRoot(x2);
        if(index1==index2){
            return true;
        }
        return false;
    }

    /**
     * 合并x1 x2
     * @param x1
     * @param x2
     */
    public void union(int x1,int x2){
        int index1=findRoot(x1);
        int index2=findRoot(x2);
        if(index1==index2){
            return;//同一个集合不允许合并
        }
        //不同集合
        elem[index1]=elem[index1]+elem[index2];
        elem[index2]=index1;//此时不再是根节点，修改双亲指向；
    }

    /**
     * 记录有效的元素个数
     * @return
     */
    public int getCount(){
        int count=0;
        for (int x:elem) {
            count++;
        }
        return count;
    }

    /**
     * 打印数组中的数
     */
    public void print(){
        for (int x:elem) {
            System.out.print(x+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int n=10;
        UnionFindSet unionFindSet=new UnionFindSet(n);
        System.out.println("合并：");
        unionFindSet.union(0,6);
        unionFindSet.union(6,7);
        unionFindSet.union(7,8);
        unionFindSet.union(1,4);
        unionFindSet.union(4,9);
        unionFindSet.union(2,3);
        unionFindSet.union(3,5);
        unionFindSet.print();
        System.out.println("判断是否在同一集合：");
        System.out.println(unionFindSet.isSameUnionFindSet(7, 8));
        System.out.println(unionFindSet.isSameUnionFindSet(0, 1));
    }
}

4.并查集的题目

1.力扣547.省份的数量
2.力扣990.等式方程的可满足性