并查集(基础+带权以及可撤销并查集后期更新)

2024-04-06 04:44

本文主要是介绍并查集(基础+带权以及可撤销并查集后期更新),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

并查集

并查集是一种图形数据结构,用于存储图中结点的连通关系。

每个结点有一个父亲,可以理解为“一只伸出去的手”,会指向另一个点,初始时指向自己。一个点的根节点是该点的父亲的父亲的..的父亲,直到某个点的父亲是自己(根)。

当两个点的根相同时,我们就说他们时同一类,或者是连通的。

如下:7,5,1,3,6的根都是3,所以他们是连通的。

2,4是连通的,而2,6不连通,因为他们的根不同。

找根的方法

如果当前点不是根,就返回父亲的根。否则就是自己

用递归的方法实现

int find(int x)

{

        if(pre[x]==x)retrun x;

        return find(pre[x]);

}

并查集的合并

在并查集中所有的操作都在根上,假如我要使x和y两个点合并,我们只需要将find(x)指向find(y)或者find(y)指向find(x);

pre[find(x)]=find(y);

假如我们要合并4和6两点,我们只需要将2指向3或将3指向2.

路径压缩

找根函数的复杂度最坏情况下会达到O(n),如果查询次数较多的话效率将会非常低下。

我们可以在找根的过程中,将父亲指向根,从而实现路径压缩,这样可以使得找根的总体时间的复杂度为O(log n)。如下图,执行一次root(7)之后,沿途的点都会直接指向根3

int  find(int x){

        return pre[x]=(pre[x]==x?x:find(pre[x]));//当前的这个点是否是根,是根的话直接输出x不是根的话,去寻中这个根

}

例题

蓝桥幼儿园

题目描述

蓝桥幼儿园的学生是如此的天真无邪,以至于对他们来说,朋友的朋友就是自己的朋友。

小明是蓝桥幼儿园的老师,这天他决定为学生们举办一个交友活动,活动规则如下:

小明会用红绳连接两名学生,被连中的两个学生将成为朋友。

小明想让所有学生都互相成为朋友,但是蓝桥幼儿园的学生实在太多了,他无法用肉眼判断某两个学生是否为朋友。于是他起来了作为编程大师的你,请你帮忙写程序判断某两个学生是否为朋友(默认自己和自己也是朋友)。

输入描述

第 11 行包含两个正整数N,M,其中 N 表示蓝桥幼儿园的学生数量,学生的编号分别为1∼N。

之后的第2∼M+1 行每行输入三个整数op,x,y:

  • 如果 op=1,表示小明用红绳连接了学生 x 和学生 y 。
  • 如果 op=2,请你回答小明学生 x 和 学生 y 是否为朋友。

输出描述

对于每个op=2 的输入,如果 x 和 y 是朋友,则输出一行 YES,否则输出一行 NO

输入输出样例

示例 1

输入

5 5 
2 1 2
1 1 3
2 1 3
1 2 3 
2 1 2

输出

NO
YES
YES

代码 

package chsi;
import java.util.*;
public class chapter1 {static int []pre;//定义一个数组表示每个结点的根是指向谁的public static void main(String[] args) {// TODO Auto-generated method stubScanner scan=new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();pre=new int[n];//初始化prefor(int i=0;i<n;i++) pre[i]=i;//初始根都是指向它本身for(int i=0;i<m;i++) {int op=scan.nextInt();int x=scan.nextInt()-1;int y=scan.nextInt()-1;if(op==1) {union(x,y);}else {x=find(x);y=find(x);if(x==y) {System.out.println("YES");}else	System.out.println("No");}}}public static int find(int x) {if(pre[x]!=x) {pre[x]=find(pre[x]);}//表示当前结点不是我们的根节点return pre[x];}//先写一个find查询,路径压缩的方式public static void union(int x,int y) {x=find(x);y=find(y);if(x!=y) {pre[x]=y;}return;}}

 

这篇关于并查集(基础+带权以及可撤销并查集后期更新)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/879017

相关文章

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

AI行业应用(不定期更新)

ChatPDF 可以让你上传一个 PDF 文件,然后针对这个 PDF 进行小结和提问。你可以把各种各样你要研究的分析报告交给它,快速获取到想要知道的信息。https://www.chatpdf.com/

poj 1182 并查集 食物链类

题意: 有n只动物,分别编号1....n。所有动物都属于A,B,C中的一种,已知A吃B,B吃C,C吃A。 按顺序给出下面两种共K条信息: 1. x 和 y 属于同一类。 2. x 吃 y 。 然而这些信息可能会出错,有可能有的信息和之前给出的信息矛盾,也有的信息可能给出的 x 和 y 不在n的范围内。 求k条信息中有多少条是不正确的。 解析: 对于每只动物,创建3个元素 i

GIS图形库更新2024.8.4-9.9

更多精彩内容请访问 dt.sim3d.cn ,关注公众号【sky的数孪技术】,技术交流、源码下载请添加微信:digital_twin123 Cesium 本期发布了1.121 版本。重大新闻,Cesium被Bentley收购。 ✨ 功能和改进 默认启用 MSAA,采样 4 次。若要关闭 MSAA,则可以设置scene.msaaSamples = 1。但是通过比较,发现并没有多大改善。

【Linux 从基础到进阶】Ansible自动化运维工具使用

Ansible自动化运维工具使用 Ansible 是一款开源的自动化运维工具,采用无代理架构(agentless),基于 SSH 连接进行管理,具有简单易用、灵活强大、可扩展性高等特点。它广泛用于服务器管理、应用部署、配置管理等任务。本文将介绍 Ansible 的安装、基本使用方法及一些实际运维场景中的应用,旨在帮助运维人员快速上手并熟练运用 Ansible。 1. Ansible的核心概念

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close