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;
        }
    }
}

到此这篇关于java实现并查集示例详解的文章就介绍到这了,更多相关java 并查集内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！