并查集算法详解

文章目录

- 并查集概念
- 并查集的常见操作
- - 构建并查集
  - 合并并查集和查找
- 关于find函数

并查集概念

并查集（Union-Find）是一种树型的数据结构，用于处理一些不交集的合并及查询问题。其主要应用是判断两个元素是否在同一个集合中，以及合并两个集合。

并查集的常见操作

构建并查集

java">public class Main12 
{public static void main(String[] args) {int[] father=new int[11];for(int i=1;i<=10;i++){father[i]=i;}}
}

这样构建的数组的每一个元素都是一个单独的集合没有任何交集。
就像这样
在这里插入图片描述

合并并查集和查找

java">public class Main12
{static int[] father=new int[11];public static void main(String[] args) {for(int i=1;i<=10;i++){father[i]=i;}father[find(1)]=find(2);father[find(3)]=find(2);father[find(2)]=find(4);}public static int find(int x){while(x!=father[x]){x=father[x];}return father[x];}
}

father数组里面存是当前元素的父节点，看个图片就理解了。
find函数是查找元素的根节点
以这个并查集为例子：
father[find(1)]=find(2);
father[find(3)]=find(2);
father[find(2)]=find(4);

在这里插入图片描述
我们先将集合1合并到集合2，再将集合3合并到集合2，最后将集合2合并到集合4。
集合的合并：例如合并集合1和集合2 father[find(1)]=find(2);就是将2的根节点赋值给1的根节点就可以了

在这里插入图片描述
看这幅图片就可以很好理解father数组里面存是当前元素的父节点
在并查集里面只有根节点的x==[father[x],通过这个特点我们可以查找集合元素的根节点，当两个元素根节点相同时则属于同一个集合，否则就不在同一集合。

关于find函数

java">public static int find(int x){while(x!=father[x]){x=father[x];}return father[x];}

我们以这种写法找根节点的时候如果我们查找n-1元素的根节点的时候需要将整棵树遍历一遍效率比较低。
在这里插入图片描述
find的第二种写法

java"> public static int find(int x){if(father[x]!=x){father[x]=find(father[x]);}return father[x];}

这种写法有个名字叫路径压缩，效率高，但是有个缺点就是会破坏树的结构。
举个例子：
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
看第一幅图我们可以知道1的父节点应该是2，但是如果使用路径压缩，1的父节点被修改为了1。意味着树的结构变为了这样

大家根据具体的需要选择合适的find方法。
并查集模板练习

java">import java.util.Scanner;
public class Main
{static int N,M;static int[] arr;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);N=scanner.nextInt();M=scanner.nextInt();arr=new int[N+10];for(int i=1;i<=N;i++){arr[i]=i;}while((M--)>0){int z=scanner.nextInt();int x=scanner.nextInt();int y=scanner.nextInt();if(z==1){arr[find(x)]=find(y);}else{if(find(x)==find(y)){System.out.println("Y");}else{System.out.println("N");}}}}static int find(int x) {if (x != arr[x]) arr[x] = find(arr[x]);return arr[x];}
}

村村通题目练习

java">import java.util.Scanner;
public class Main
{static int N,M;static int[] arr;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);N=scanner.nextInt();M=scanner.nextInt();arr=new int[N+10];for(int i=1;i<=N;i++){arr[i]=i;}while((M--)>0){int z=scanner.nextInt();int x=scanner.nextInt();int y=scanner.nextInt();if(z==1){arr[find(x)]=find(y);}else{if(find(x)==find(y)){System.out.println("Y");}else{System.out.println("N");}}}}static int find(int x) {if (x != arr[x]) arr[x] = find(arr[x]);return arr[x];}
}