文章目录
- 并查集概念
- 并查集的常见操作
- 构建并查集
- 合并并查集和查找
- 关于find函数
并查集概念
并查集(Union-Find)是一种树型的数据结构,用于处理一些不交集的合并及查询问题。其主要应用是判断两个元素是否在同一个集合中,以及合并两个集合。
并查集的常见操作
构建并查集
public class Main12
{public static void main(String[] args) {int[] father=new int[11];for(int i=1;i<=10;i++){father[i]=i;}}
}
这样构建的数组的每一个元素都是一个单独的集合没有任何交集。
就像这样
合并并查集和查找
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函数
public static int find(int x){while(x!=father[x]){x=father[x];}return father[x];}
我们以这种写法找根节点的时候如果我们查找n-1元素的根节点的时候需要将整棵树遍历一遍效率比较低。
find的第二种写法
public static int find(int x){if(father[x]!=x){father[x]=find(father[x]);}return father[x];}
这种写法有个名字叫路径压缩,效率高,但是有个缺点就是会破坏树的结构。
举个例子:
看第一幅图我们可以知道1的父节点应该是2,但是如果使用路径压缩,1的父节点被修改为了1。意味着树的结构变为了这样
大家根据具体的需要选择合适的find方法。
并查集模板练习
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];}
}
村村通题目练习
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];}
}
完。