并查集（基础+带权以及可撤销并查集后期更新）

并查集

并查集是一种图形数据结构，用于存储图中结点的连通关系。

每个结点有一个父亲，可以理解为“一只伸出去的手”，会指向另一个点，初始时指向自己。一个点的根节点是该点的父亲的父亲的..的父亲，直到某个点的父亲是自己（根）。

当两个点的根相同时，我们就说他们时同一类，或者是连通的。

如下：7，5，1，3，6的根都是3，所以他们是连通的。

2，4是连通的，而2，6不连通，因为他们的根不同。

找根的方法

如果当前点不是根，就返回父亲的根。否则就是自己

用递归的方法实现

int find(int x)

{

        if(pre[x]==x)retrun x;

        return find(pre[x]);

}

并查集的合并

在并查集中所有的操作都在根上，假如我要使x和y两个点合并，我们只需要将find(x)指向find(y)或者find(y)指向find(x);

pre[find(x)]=find(y);

假如我们要合并4和6两点，我们只需要将2指向3或将3指向2.

路径压缩

找根函数的复杂度最坏情况下会达到O(n),如果查询次数较多的话效率将会非常低下。

我们可以在找根的过程中，将父亲指向根，从而实现路径压缩，这样可以使得找根的总体时间的复杂度为O(log n)。如下图，执行一次root(7)之后，沿途的点都会直接指向根3

int  find(int x){

        return pre[x]=(pre[x]==x?x:find(pre[x]));//当前的这个点是否是根，是根的话直接输出x不是根的话，去寻中这个根

}

例题

蓝桥幼儿园

题目描述

蓝桥幼儿园的学生是如此的天真无邪，以至于对他们来说，朋友的朋友就是自己的朋友。

小明是蓝桥幼儿园的老师，这天他决定为学生们举办一个交友活动，活动规则如下：

小明会用红绳连接两名学生，被连中的两个学生将成为朋友。

小明想让所有学生都互相成为朋友，但是蓝桥幼儿园的学生实在太多了，他无法用肉眼判断某两个学生是否为朋友。于是他起来了作为编程大师的你，请你帮忙写程序判断某两个学生是否为朋友（默认自己和自己也是朋友）。

输入描述

第 11 行包含两个正整数N,M，其中 N 表示蓝桥幼儿园的学生数量，学生的编号分别为1∼N。

之后的第2∼M+1 行每行输入三个整数op,x,y：

• 如果 op=1，表示小明用红绳连接了学生 x 和学生 y 。
• 如果 op=2，请你回答小明学生 x 和 学生 y 是否为朋友。

输出描述

对于每个op=2 的输入，如果 x 和 y 是朋友，则输出一行 YES，否则输出一行 NO。

输入输出样例

示例 1

输入

5 5 
2 1 2
1 1 3
2 1 3
1 2 3 
2 1 2

输出

NO
YES
YES

代码 

package chsi;
import java.util.*;
public class chapter1 {static int []pre;//定义一个数组表示每个结点的根是指向谁的public static void main(String[] args) {// TODO Auto-generated method stubScanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();pre=new int[n];//初始化prefor(int i=0;i<n;i++) pre[i]=i;//初始根都是指向它本身for(int i=0;i<m;i++) {int op=scan.nextInt();int x=scan.nextInt()-1;int y=scan.nextInt()-1;if(op==1) {union(x,y);}else {x=find(x);y=find(x);if(x==y) {System.out.println("YES");}else	System.out.println("No");}}}public static int find(int x) {if(pre[x]!=x) {pre[x]=find(pre[x]);}//表示当前结点不是我们的根节点return pre[x];}//先写一个find查询，路径压缩的方式public static void union(int x,int y) {x=find(x);y=find(y);if(x!=y) {pre[x]=y;}return;}}