佛山附近做网站的公司,企业网站首页效果图,中国核工业二三建设有限公司招聘信息,新创建的网站目录
#x1f9d0;一.并查集的基本概念实例#xff1a;
#x1f92a;二.并查集代码#xff1a;
#x1f602;三#xff1a;并查集的一些习题#xff1a;
A.省份数量
B.等式方程的可满足性 #x1f9d0;一.并查集的基本概念实例#xff1a; 并查集概念一.并查集的基本概念实例
二.并查集代码
三并查集的一些习题
A.省份数量
B.等式方程的可满足性 一.并查集的基本概念实例 并查集概念将n个不同的元素划分成一些不相交的集合。开始时每个元素自成一个单元素集合然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。 有了上面的一定了解我们再来看一个实例
比如某公司今年校招全国总共招生10人西安招4人成都招3人武汉招3人10个人来自不同的学校 起先互不相识每个学生都是一个独立的小团体现给这些学生进行编号{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 给以下 数组用来存储该小集体数组中的数字代表该小集体中具有成员的个数。(负号下文解释) 毕业后学生们要去公司上班每个地方的学生自发组织成小分队一起上路于是 西安学生小分队s1{0,6,7,8}成都学生小分队s2{1,4,9}武汉学生小分队s3{2,3,5}就相互认识了10个 人形成了三个小团体。假设右三个群主0,1,2担任队长负责大家的出行。 一趟火车之旅后每个小分队成员就互相熟悉称为了一个朋友圈。 在公司工作一段时间后西安小分队中8号同学与成都小分队1号同学奇迹般的走到了一起两个小圈子的学生相互介绍最后成为了一个小圈子 现在0集合有7个人2集合有3个人总共两个朋友圈,负数的个数就是集合的个数 注意事项 我们一般将数组中的元素初始化为-1 (数组的下标:) 数组的下标对应集合中元素的编号 数组的值array[i]: 数组中如果为负数负号代表根数字代表该集合中元素个数 数组的值array[i]:数组中如果为非负数代表该元素双亲在数组中的下标 并查集能干的事 查找元素属于哪个集合 沿着数组表示树形关系以上一直找到根(即树中中元素为负数的位置) 查看两个元素是否属于同一个集合 沿着数组表示的树形关系往上一直找到树的根如果根相同表明在同一个集合否则不在 将两个集合归并成一个集合 将两个集合中的元素合并 将一个集合名称改成另一个集合的名称
二.并查集代码
import java.util.*;
public class UnionFindSet {public int[] elem;public UnionFindSet(int n){this.elem new int[n];Arrays.fill(elem,-1);}//查询x的根节点返回根节点的下标public int findRoot(int x){if(x 0){throw new IndexOutOfBoundsException(下标不合法是负数);}//一直等到数组里面的值为负数时才找到一个根while(elem[x] 0){x elem[x];}return x;}//查询x1和x2是否是同一个集合public boolean isSameUnionFindSet(int x1,int x2){int index1 findRoot(x1);int index2 findRoot(x2);if(index1 index2) return true;return false;}//这是合并操作public void union(int x1,int x2){int index1 findRoot(x1);int index2 findRoot(x2);if(index1 index2){return ;}elem[index1] elem[index1] elem[index2];elem[index2] index1;}//查询集合的个数public int getCount(){int count 0;for(int x : elem){if(x 0) count;}return count;}
}那我们趁热打铁来做两道题练习一下
三并查集的一些习题 A.省份数量 题目链接. - 力扣LeetCode 思路我们初始化一个一维数组表示并查集数组大小为城市的个数遍历这个二维数组isConnected[i][j] 表示 i , j 两个城市相连用并查集将相连接的城市合并到一个集合中最后统计集合中元素的个数就是要求的省份个数 class Solution {//A.省份数量public int findCircleNum(int[][] isConnected) {int n isConnected.length;UnionFindSet ufs new UnionFindSet(n);//将连接在一起的城市合并for(int i 0;i isConnected.length;i){for(int j 0;j isConnected[0].length;j){if(isConnected[i][j] 1){ufs.union(i,j);}}}//查找连接在一起的城市即省份的个数直接返回return ufs.getCount();}
}
/* 并查集的实现*/
class UnionFindSet {public int[] elem;public UnionFindSet(int n){this.elem new int[n];Arrays.fill(elem,-1);}//查询x的根节点返回根节点的下标public int findRoot(int x){if(x 0){throw new IndexOutOfBoundsException(下标不合法是负数);}while(elem[x] 0){x elem[x];}return x;}//查询x1和x2是否是同一个集合public boolean isSameUnionFindSet(int x1,int x2){int index1 findRoot(x1);int index2 findRoot(x2);if(index1 index2) return true;return false;}//这是合并操作public void union(int x1,int x2){int index1 findRoot(x1);int index2 findRoot(x2);if(index1 index2){return ;}elem[index1] elem[index1] elem[index2];elem[index2] index1;}//查询集合的个数public int getCount(){int count 0;for(int x : elem){if(x 0) count;}return count;}}运行结果 B.等式方程的可满足性 题目链接. - 力扣LeetCode 思路我们将具有相同属性的元素放入一个集合中接着再遍历一遍字符串数组如果字符串中对应的元素是说明不是一个集合再从上述并查集中查找 如果是一个集合的(矛盾了)返回false;遍历完成后也没有返回false那么这个等式方程组就满足条件 class Solution {//B.等式方程的可满足性public boolean equationsPossible(String[] equations) {UnionFindSet ufs new UnionFindSet(26);//将具有相同属性的元素放入一个集合中for(int i 0;i equations.length;i){if(equations[i].charAt(1) ){ufs.union(equations[i].charAt(0) - a,equations[i].charAt(3) - a);}}//如果字符串中对应的元素是说明不是一个集合再从上述并查集中查找 (矛盾了)如果是一个集合的返回false;for(int i 0;i equations.length;i){if(equations[i].charAt(1) !){//查找根节点的下标位置int index1 ufs.findRoot(equations[i].charAt(0) - a);int index2 ufs.findRoot(equations[i].charAt(3) - a);if(index1 index2) return false;}}return true;}
}
/* 并查集的实现 */
class UnionFindSet {public int[] elem;public UnionFindSet(int n){this.elem new int[n];Arrays.fill(elem,-1);}//查询x的根节点返回根节点的下标public int findRoot(int x){if(x 0){throw new IndexOutOfBoundsException(下标不合法是负数);}while(elem[x] 0){x elem[x];}return x;}//查询x1和x2是否是同一个集合public boolean isSameUnionFindSet(int x1,int x2){int index1 findRoot(x1);int index2 findRoot(x2);if(index1 index2) return true;return false;}//这是合并操作public void union(int x1,int x2){int index1 findRoot(x1);int index2 findRoot(x2);if(index1 index2){return ;}elem[index1] elem[index1] elem[index2];elem[index2] index1;}//查询集合的个数public int getCount(){int count 0;for(int x : elem){if(x 0) count;}return count;}
}
运行结果 结语 写博客不仅仅是为了分享学习经历同时这也有利于我巩固知识点总结该知识点由于作者水平有限对文章有任何问题的还请指出接受大家的批评让我改进。同时也希望读者们不吝啬你们的点赞收藏关注你们的鼓励是我创作的最大动力
