Java 并查集

时间:2022-05-23 水公子人气:0

题目

题目背景

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

思路

对于该题而言，考察的是并查集，也就是小怪兽逐个找上级领导的思路，指导找到最终的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;
        }
    }
}

加载全部内容