并查集模板-两个操作:合并集合和查询两个元素是否属于同一个集合

这篇具有很好参考价值的文章主要介绍了并查集模板-两个操作:合并集合和查询两个元素是否属于同一个集合。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、链接

836. 合并集合

二、题目

一共有 nn 个数,编号是 1∼n1∼n,最开始每个数各自在一个集合中。

现在要进行 mm 个操作,操作共有两种

  1. M a b,将编号为 aa 和 bb 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作;
  2. Q a b询问编号为 aa 和 bb 的两个数是否在同一个集合中
输入格式

第一行输入整数 nn 和 mm。

接下来 mm 行,每行包含一个操作指令,指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b,都要输出一个结果,如果 aa 和 bb 在同一集合内,则输出 Yes,否则输出 No

每个结果占一行。

数据范围

1≤n,m≤1051≤n,m≤105

输入样例:
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例:
Yes
No
Yes
难度:简单
时/空限制:1s / 64MB
总通过数:80710
总尝试数:127618
来源:模板题,AcWing
算法标签

挑战模式

三、题意

题目的意思比较简单,就是将两个元素合并到同一个集合,然后随便给定两个元素,判断这两个元素是否属于同一个集合

属于模板题目 

四、代码

#include<iostream>

using namespace std;

const int N=1e5+10;

int p[N];

int find(int x)
{
    if(x!=p[x])
    {
        p[x]=find(p[x]);
    }
    
    return p[x];
}

int main()
{
    int n,m;
    
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
    }
    
    while(m--)
    {
        char op[2];
        int a,b;
        
        scanf("%s%d%d",op,&a,&b);
        if(op[0]=='M')
        {
            p[find(a)]=find(b);
        }
        else
        {
            if(find(a)==find(b))
            {
                printf("Yes\n");
            }
            else
            {
                printf("No\n");
            }
        }
    }
    
    return 0;
}

五、总结

1.并查集:实现两种操作,第一种是将两个元素合并到一个集合(改变一个元素的根节点指向另一个元素的根节点即可),第二种是查询给定的两个元素是否属于同一个集合(判断这两个数的根节点是否相同

2.所以核心就是在根节点上进行操作

3.数据范围是1e5,可以给每一个数据分配一个下标,表示节点,也就是代码里面的初始化操作

for(int i=1;i<=n;i++)
{
    p[i]=i;
}

注意这里要从1开始循环,因为题目给的数据从1到n 

4.p[]数组现在下标等于数值,给定一个数值可以找到具体的结点是哪一个,因为题目的特殊性质(只需要实现查询两个元素是否属于同一个集合,只需要输出yes/no),所以我们可以进一步优化,让每一个结点直接指向根节点,也就是p[]直接等于根节点的数值,假设根节点是p[3]=3,属于同一个集合的还有,4,5,6,7,那么有p[4],p[5],p[6],p[7]都等于3

5.路径压缩说的就是把所有节点都指向根节点:实现的代码就是这一行:

if(p[x]!=x)
{
    p[x]=find(p[x]);
}

迭代的思想,只有根节点的下标等于本身数值,其他的结点的数值都不等于下标(这里是指经过合并操作之后的,初始化之后所有结点,下标都等于数值,也可以理解成最开始有n个根节点,合并操作之后,会把结点的数值进行修改),节点的数值等于根节点的数值,下标表示的是原来这个数字。只有下标和数值相等了,才会返回数值,也就是返回根节点

6.把两个元素合并到同一个集合:让a的根节点指向b的根节点,把a的根节点也修改一遍,那么相应的,所有以a为根节点的结点,都要发生改变,实现的代码是这一行

p[find(a)]=find(b);

find(a)找到的是a的根节点的数值,根据根节点数值和下标相等,p[find(a)]表示的是纯正的根节点,比如p[3]=3这种根节点,把另一个元素的根节点的数值赋给这个元素,表示的是把根节点换了,以前a的根节点现在以前把a的根节点当作根节点的,现在把b的根节点当作根节点,反正就是find函数里面迭代,一直找到下标等于数值的才会停止 

7.查询两个元素是否属于同一个集合:直接看他们的根节点是否相等就好了。

8.本质其实挺简单的,但是理解代码感觉还是有些难度,比较绕,既然是模板题目,记住算法思路和写法,然后可以熟练的默写出来就可以了。

六、精美图片

并查集模板-两个操作:合并集合和查询两个元素是否属于同一个集合,算法竞赛,算法,图论,c++,数据结构,leetcode,蓝桥杯,开发语言

 文章来源地址https://www.toymoban.com/news/detail-635768.html

到了这里,关于并查集模板-两个操作:合并集合和查询两个元素是否属于同一个集合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图论:并查集的合并、判断和求节点

     所谓并查集就是可以画图理解 假如说我们想要构建一个树(也是图),要求1-2,2-4,1-3 在构另一个树,要求5-6,6-7,5-8 1是2的头结点,2是4的头结点,以此类推 下面要求去将5连接到1上,就是我下面要讲的,其实上面的子节点的连接也是如此的。 简单并查集例题: 一共有 n 个数

    2024年01月18日
    浏览(35)
  • 【数据结构】并查集的简单实现,合并,查找(C++)

    需要将n个不同的元素 划分成一些不相交的集合 。开始时,每个元素自成一个单元素集合,然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。 学生小

    2024年02月04日
    浏览(49)
  • 【算法每日一练]-图论(保姆级教程篇7 最小生成树 ,并查集模板篇)#村村通 #最小生成树

    目录 题目:村村通 并查集  题目:最小生成树 kruskal算法 prim算法          先引入问题: 要在n个城市之间铺设光缆,主要目标是要使这 n 个城市的 任意两个之间都可以通信 ,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此另一个目标是要 使铺设光

    2024年02月04日
    浏览(76)
  • 并查集(种类并查集,带权并查集)

    链接:登录—专业IT笔试面试备考平台_牛客网 来源:牛客网   动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B,B吃C,C吃A。 现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所

    2024年02月11日
    浏览(38)
  • 12.25~12.27并查集(查找与合并),全排列,约瑟夫问题(队列,数组)upper/lower_bound,重构二叉树,最优矩阵,线段树(构建),淘汰赛(构建树,队列),医院问题(最短路,弗洛伊德

    题目背景 若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 题目描述 规定:�x 和 �y 是亲戚,�y 和 �z 是亲戚,那么 �x 和 �z 也是亲戚。如果 �x,�y 是亲戚,那么 �

    2024年01月23日
    浏览(47)
  • C语言实现两个集合合并及有序集合的并集(顺序存储、链式存储)

    1、两个集合并集问题 获取LA、LB的表长m、n。 从LB中第一个数据元素开始,循环n次执行:从LB中查找第i(1≤i≤n)个数据元素赋值给e;然后在LA中查找元素e,如果不存在,则将e插入在表LA的最后。 2、算法描述 3、顺序存储实现 4、链式存储实现

    2024年02月07日
    浏览(53)
  • 27.移除元素+88.合并两个有序数组

    目录 一、移除元素 (一)题目 (二)代码  二、合并两个有序数组 (一)题目 (二)代码 27. 移除元素 - 力扣(LeetCode)     88. 合并两个有序数组 - 力扣(LeetCode)    用双指针  

    2023年04月14日
    浏览(40)
  • Stream流 - 两个list集合对象属性的合并、对象属性值运算

    📅 合并两个 list<map>, 并将 userId 相同的所有属性合并到一个 map 中 list1中对象的属性:userId、userName list2中对象的属性:userId、gender、age 📌 最终总集合中对象的属性:userId、userName、gender、age 运行结果: 结果可见,userId 相同的所有属性合并到集合 list1中。 📅 合并两个

    2024年02月06日
    浏览(123)
  • 【数据结构】并查集

    并查集是简单的数据结构,学会并查集,为图打好基础。 是树状的数据结构,用于处理相交集合的合并与查询 通常用森林表示,一片森林表示一个集合 并查集一般需要完成 查找元素属于哪个集合 查看两个元素是否属于同一个集合 将两个集合归并成一个集合 集合的个数 假

    2024年02月19日
    浏览(36)
  • 【高阶数据结构】——并查集

    在一些应用问题中, 需要将n个不同的元素划分成一些不相交的集合。开始时,每个元素自成一个单元素集合, 然后按一定的规律将归于同一组元素的集合合并 。在此过程中要 反复用到查询某一个元素归属于那个集合的运算 。适合于描述这类问题的抽象数据类型称为 并查集

    2024年02月16日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包