Java实现并查集示例详解
作者:水公子 发布时间:2023-07-17 05:41:34
题目
题目背景
若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。
思路
对于该题而言,考察的是并查集,也就是小怪兽逐个找上级领导的思路,指导找到最终的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
猜你喜欢
- 本文实例讲述了C#封装的常用文件操作类。分享给大家供大家参考。具体如下:这个C#类封装了我们经常能用到的文件操作方法,包括读写文件、获取文件
- 使用ProcessBuilder踩到的坑最近使用ProcessBuilder执行命令,命令内容正确,但始终报错命令实行失败,是因为不熟悉Pr
- 我就废话不多说了,大家还是直接看代码吧~private LineRenderer line;//画线line = this.gameObje
- 基础配置新建module:cloudalibaba-config-nacos-client3377pom文件版本号已经由父工程控制<?
- 前言通过Mybatis做7000+数据量的批量插入的时候报错了,error log如下: , ('G61010352', &
- 微信支付最近公司要在微信公众号上做一个活动预报名,活动的门票等需要在微信中支付。微信支付前的准备微信支付需要一个微信支付商务号(https:
- 详解path和classpath的区别path的作用path是系统用来指定可执行文件的完整路径,即使不在path中设置JDK的路径也可执行J
- Activiti项目是一项新的基于Apache许可的开源BPM平台,本文就来简述一下Activiti常用类。具体如下:一、为什么要使用工作流
- 如下所示:import javax.xml.parsers.DocumentBuilderFactory;import javax.xml.
- 开发一款App,总会遇到各种各样的需求和业务,这时候选择一个简单好用的轮子,就可以事半功倍前言 Intent intent =
- 一般而言,一个项目部署的由:拉取代码->构建->测试->打包->部署等过程组成,如果我们经常需要部署项目,特别是在微
- 这阵子在做Lephone的适配,测试组提交一个bug:标题栏的文字较长时没有显示完全,其实这并不能算个bug,并且这个问题在以前其他机器也没
- 如果在类路径上添加了Spring Boot Security依赖项,则Spring Boot应用程序会自动为所有HTTP端点提供基本身份验证
- filter自定义过滤器 增加了 对验证码的校验package com.youxiong.filter;import com.y
- 拿到了项目框架工程代码却没有uml图,那么方法之间的调用关系功能流转就不容易看出来,那么如何产生类图呢,记忆里方法有下:1.rose逆向工程
- 1)下载sqlite jdbc驱动http://www.xerial.org/maven/repository/artifact/org/x
- mybatis实体类字段大小写问题 字段获取不到值由于前期设计问题,项目中需要用到的一个字段 rootpath,所以我再实体层加了这么一个字
- 1.导入System.Runtime.InteropServices命名空间。2.API函数ShowWindow()能够控制人和窗体的现实状
- 首先在pom文件里引入mqtt的依赖配置<!--mqtt--> <d
- 一、项目简述功能包括:用户分为宠物,医生,管理员,宠物主人可进行注册选择医生挂号,选择日期,选择号源,医生可进行宠物接诊,管理员可对宠物,医