并查集算法详解
并查集概念
并查集（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];
}
}
完。
原文地址：https://blog.csdn.net/2403_82759827/article/details/143607579
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！