Java实现并查集示例详解

题目

题目背景

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

思路

对于该题而言，考察的是并查集，也就是小怪兽逐个找上级领导的思路，指导找到最终的Boss停止下来，如果两个怪兽要打架，需要问一问他们的上级领导，领导再问领导，逐级向上，最终发现它们属于同一个Boss的部署的话就不能再打架了，这道题同样的思路，如果斗罗大陆的一开始白沉香不知道唐三是亲戚的话，他们就会先询问自己的祖辈，而白沉香通过她爷爷得知她和唐三有亲戚，那么他们就不会再打起来，而是会联盟，一起去打别的敌人，同样，我的亲戚是你，你的亲戚是她，那么我和她也就会是亲戚，就像老家里你堂哥是你亲戚，你堂哥和他姥爷是亲戚，那么你就和他姥爷是亲戚

find实现

这个find就是用来查找他们的上级的，初始化时小怪兽高兴坏了，认为自己就是自己的上司，我就是王，我就是Boss，这么想其实也并没有错，毕竟自己在井底，那么，就用数组pre[]来存他们的上一级，例如：pre[10]=6;那么就认为10的上级就是6，6的上级假设是4，4的上级加入是自己，也即是 pre[4]=4;这时为4的怪兽就理解了，原来自己的上级是自己，那自己就是王了，这时就找到了boss,回想刚刚说的，两个怪兽如果想要打架，就需要先问问各自的上级，如果上级再问上级直到问到他们属于同一个boss，这时它们就会微笑说，原来我们属于同一个领导，那么find就是用来找最终两个分队的怪兽最终的领导的

public static int find(int x){
       if(pre[x]==x)return x;//如果上级领导是自己，就返回自己
       return pre[x]=find(pre[x]);//如果不是，就逐一进行访问上级，直到找到boss,这里相当于最终找到了boss,把boss赋值给pre[x]
   }

join的实现

join是用来干嘛的呢？它是用来合并的，加入有两个大王，它们各自占山为王，势力不相上下，实力也不相上下，有一天发生变故，大王1就想和大王2进行合并，大王二琢磨着合并后谁当大王？不能让它当了大王，大王2于是就说合并后我来当大王，大王一显然会不同意，大王二说你来找我合并的，不同意也要同意，于是大王二当成了 大王，这时大王二掌握了所有的军队，包括大王一的，那么join就是用来选两个大王其中一个作为总大王的。

public static void join(int x,int y){
       int xx=find(x);//用find找到第一个大王
       int yy=find(y);//找到第二个大王
       if(xx!=yy){//如果不相等
           pre[xx]=yy;//将其中一个大王统领第一个大王所有的军队
       }

整体代码 

import java.util.Scanner;
public class test1 {
   static  int []pre=new int[10000];//注意题目中范围
   public static void main(String[] args) {
       int n,m,p,x,y;
       Scanner sc=new Scanner(System.in);
       n=sc.nextInt();//n个人
       m=sc.nextInt();//m对关系
       p=sc.nextInt();//p询问关系
       for(int i = 0; i < n; i++){
           pre[i]=i;//初始化，自己的祖先是自己
       }
       for(int i = 0; i < m; i++){
           x=sc.nextInt();
           y= sc.nextInt();
           join(x,y);//合并
       }

for(int i = 0; i <p;i++){
           x=sc.nextInt();
           y= sc.nextInt();
           if(find(x)==find(y)){
               System.out.print("Yes");
           }else{
               System.out.print("No");
           }
       }
   }
   public static int find(int x){
       if(pre[x]==x)return x;
       return pre[x]=find(pre[x]);
   }
   public static void join(int x,int y){
       int xx=find(x);
       int yy=find(y);
       if(xx!=yy){
           pre[xx]=yy;
       }
   }
}

来源：https://blog.csdn.net/weixin_52924633/article/details/121829960