Java实现并查集示例详解

Java实现并查集示例详解

目录题目思路find实现join的实现整体代码

题目

题目背景

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

思路

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

find实现

这个find就是用来查找他们的上级的，初始化时小怪兽高兴坏了，认为自己http://就是自己的上司，我就是王，我就是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;//将其中一个大王统领第一个大王所有的军队

}

整体代码

imporDcXLowt 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

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;

}

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。