Java实现并查集示例详解
目录
- 题目
- 思路
- find实现
- join的实现
- 整体代码
题目
题目背景
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
思路
对于该题而言，考察的是并查集，也就是小怪兽逐个找上级领导的思路，指导找到最终的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 并查集内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
Java实现并查集
本文实例为大家分享了Java实现并查集的具体代码,供大家参考,具体内容如下 自下而上的树结构 接口 /** * @author Nino */ public interface UF { int size(); /** * 看两个元素是否相连 * @param p * @param q * @return */ boolean isConnected(int p, int q); /** * 将两个元素合并在一起,变成一个集合中的元素 * @param p * @param q */ void
-
Java实现快速并查集
在一些应用的问题中,需将n个不同的元素划分成一组不相交的集合.开始时,每个元素自成一格单元素集合,然后按一定顺序将属于同一组的元素的集合合并.其间要反复用到查询某个元素属于哪个集合的运算.适合于描述这类问题的抽象数据类型称为并查集. 1. 并查集的概述 并查集的数学模型是一组不相交的动态集合的集合S={A,B,C,...},它支持以下的运算: (1)union(A,B):将集合A和B合并,其结果取名为A或B: (2)find(x):找出包含元素x的集合,并返回该集合的名字. 在并查集中需要两个类
-
java并查集算法带你领略热血江湖
目录 一.什么是并查集 二.深入理解并查集 三.实现并查集 四.真题训练 五.路径压缩优化 六.总结 你好,我是小黄,一名独角兽企业的Java开发工程师. 校招收获数十个offer,年薪均20W~40W. 感谢茫茫人海中我们能够相遇, 俗话说:当你的才华和能力,不足以支撑你的梦想的时候,请静下心来学习, 希望优秀的你可以和我一起学习,一起努力,实现属于自己的梦想. 一.什么是并查集 并查集被很多OIer认为是最简洁而优雅的数据结构之一,主要用于处理一些不相交集合的合并问题,并支持两种操作: 合并
-
详解Java实现数据结构之并查集
一.什么是并查集 对于一种数据结构,肯定是有自己的应用场景和特性,那么并查集是处理什么问题的呢? 并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题,常常在使用中以森林来表示.在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中.其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受:即使在空
-
Java数据机构中关于并查集的详解
目录 概念 实现 初始化并查集 判断是不是同一个组 查找当前节点的代表节点 合并操作 本期文章源码:GitHub 一文彻底搞懂<并查集>! 概念 并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题(即所谓的并.查).比如说,我们可以用并查集来判断一个森林中有几棵树.某个节点是否属于某棵树等. 具体的用法,我们会以下一篇文章<图的相关算法>中,有一个克鲁斯卡尔算法,用于生成最小生成树,会用到并查集. 并查集的主要作用是求连通分支数(如果一个图中所有点都存在可达关系(直
-
Java实现并查集示例详解
目录 题目 思路 find实现 join的实现 整体代码 题目 题目背景 若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系. 思路 对于该题而言,考察的是并查集,也就是小怪兽逐个找上级领导的思路,指导找到最终的Boss停止下来,如果两个怪兽要打架,需要问一问他们的上级领导,领导再问领导,逐级向上,最终发现它们属于同一个Boss的部署的话就不能再打架了,这道题同样的思路,如果斗罗大陆的一开始白沉香不知道唐三是亲戚的话,他们就
-
Java垃圾回收机制的示例详解
目录 一.概述 二.对象已死? 1.引用计数算法 2.可达性分析算法 3.四种引用 4.生存还是死亡? 5.回收方法区 三.垃圾收集算法 1.分代收集理论 2.名词解释 3.标记-清除算法 4.标记-复制算法 5.标记-整理算法 一.概述 说起垃圾收集(Garbage Collection,下文简称GC),有不少人把这项技术当作Java语言的伴生产 物.事实上,垃圾收集的历史远远比Java久远,在1960年诞生于麻省理工学院的Lisp是第一门开始使 用内存动态分配和垃圾收集技术的语言.当Lisp
-
Java之单例设计模式示例详解
单例设计模式 保证一个类在内存中只能有一个对象. 思路: 1)如果其他程序能够随意用 new 创建该类对象,那么就无法控制个数.因此,不让其他程序用 new 创建该类的对象. 2)既然不让其他程序 new 该类对象,那么该类在自己内部就要创建一个对象,否则该类就永远无法创建对象了. 3)该类将创建的对象对外(整个系统)提供,让其他程序获取并使用. 饿汉式: 一上来我就把对象给你 new 好了,你来了直接就可以拿去"吃"了 懒汉式 (要是有人问单例的延迟加载方式指的就是这种方式) 一开始
-
java 实现迷宫回溯算法示例详解
用一个7 x 7的矩形表示迷宫,0和1分别表示的是通路和障碍.通过设计编写程序找到蓝色小球达到蓝色旗子的路线 思路: 构建一个迷宫(用二维数组)实现找通路的方法findRoad() 构建二维数组不难,我们主要是要实现findRoad()这个方法,在实现这个方法前,我们需要约定好一下几个点:小球的位置当作入口(1,1),小旗的位置当作出口(5,5)数组里数的含义分别为(0没有走过).(1障碍).(2走过且为正确的路线).(3走过且为错误的路线)将我们每一步的走法称为策略:下 -> 右 -> 上
-
Java实现广度优先遍历的示例详解
目录 什么是广度优先 一个简单的例子 程序实现 总结 什么是广度优先 广度就是扩展开,广度优先的意思就是尽量扩展开.所以在算法实现的时候,就是一个循环遍历枚举每一个邻接点.其基本思路就是按层扩展,扩得越广越好. 伪代码如下: for(int i = 0; i < children.size(); i++){ children.get(i); // 调用每一个子节点 } 一个简单的例子 我们以一个简单的迷宫为例,以1代表墙,0代表路径,我们构造一个具有出入口的迷宫. 1 1 0 1 1 1 1 1
-
Java设计模式之适配器模式的示例详解
目录 定义 分类 案例 需求 方案一:类适配器 方案二:对象适配器 方案三:接口适配器 对比分析 方案一:类适配器 方案二:对象适配器 方案三:接口适配器 总结 定义 适配器模式,即将某个类的接口转换成客户端期望的另一个接口的表示,主要目的是实现兼容性,让原本因为接口不匹配,没办法一起工作的两个类,可以协同工作. 分类 类适配器 对象适配器 接口适配器 案例 需求 手机充电,通过手机充电器将220V电压适配为5V 方案一:类适配器 定义220V交流电(被适配者的角色) /** * 220V交流电
-
Java装饰者模式的示例详解
目录 定义 案例 需求 方案 分析 使用场景 知识点补充 定义 装饰者模式:在不改变原有对象的基础之上,动态的将功能附加到对象上,提供了继承更有弹性的替代方案,也体现了开闭原则 案例 需求 一个人去咖啡店点了一杯卡布奇诺,加了一份热牛奶 方案 定义咖啡基类 public abstract class Coffee { private String desc; private float price; public abstract float cost(); public String getD
-
Java设计模式之外观模式示例详解
目录 定义 案例 需求 方案:外观模式实现 分析 总结 定义 外观模式为多个复杂的子系统,提供了一个一致的界面,使得调用端只和这个接口发生调用,而无须关系这个子系统内部的细节 案例 需求 看电影的时候需要进行一系列的操作,比如打开播放器,放下屏幕,打开投影仪,打开音响等,这个要怎么进行管理呢 方案:外观模式实现 定义播放器类 public class Player { private static Player player = new Player(); private Player(){}
-
Java中的反射机制示例详解
目录 反射 什么是Class类 获取Class实例的三种方式 通过反射创建类对象 通过反射获取类属性.方法.构造器 更改访问权限和实例赋值 运用场景 反射 反射就是把Java类中的各个成分映射成一个个的Java对象.即在运行状态中,对于任意一个类,都能够知道这个类的所以属性和方法:对于任意一个对象,都能调用它的任意一个方法和属性.这种动态获取信息及动态调用对象方法的功能叫Java的反射机制 每一个Java程序执行必须通过编译.加载.链接和初始化四个阶段 1.编译:将.java.文件编译成字节码.