首页 > 其他分享 >acwing 合并集合

acwing 合并集合

时间:2023-02-21 19:36:08浏览次数:39  
标签:输出 int 合并 节点 集合 Yes find acwing

题目

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

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

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

输入格式

第一行输入整数 n 和 m。

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

输出格式

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

每个结果占一行。

数据范围

1≤n,m≤10^5

输入样例:

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例:

Yes
No
Yes

题解

分析

这道题目是最基础的并查集问题
可以把每一个集合都当成一棵树,然后寻找根节点,根节点就是一类集合
如果要合并两个集合,可以直接让一棵树得根节点的父节点等于另一颗树的根节点
使用一个数组来存储节点的父节点

find函数用递归的方式来寻找某节点的根节点,并且采用了路径优化,使之查询效率甚至可以几乎达到O(1)的程度

代码

#include "iostream"
using namespace std;
const int N = 100010;
int p[N]={0};
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)p[i]=i;
    while (m--){
        string op;
        int a,b;
        cin>>op>>a>>b;
        if(op=="M"){
            p[find(a)]=find(b);
        }
        else{
            if(find(a)==find(b))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

标签:输出,int,合并,节点,集合,Yes,find,acwing
From: https://www.cnblogs.com/ChengMao/p/17142128.html

相关文章

  • leetcode 56. 合并区间
    区间左端点进行排序如果intervals小于等于一个元素直接返回如果大于1个按照左边点进行排序从左至右依次合并classSolution{public:staticboolcmp(vector<int>&a,vec......
  • 列表的内置方法,字典的内置方法,元组,集合
    1.练习先进先出先进后出2.列表reverse颠倒列表内数据顺序sort从小到大排序(前提是:纯数字比较)列表的比较是比较索引对应位置的数据值,只要有一个比较出来,都不在往......
  • 2023.2.21AcWing蓝桥杯集训·每日一题
    知识点为二分。AcWing113.特殊排序题目描述有\(N\)个元素,编号\(1,2..N\),每一对元素之间的大小关系是确定的,关系具有反对称性,但不具有传递性。注意:不存在两个元素大......
  • day08 元组字典集合
    day08元组集合字典 元组"""小括号括起来,内部存放多个元素,元组之间逗号隔开,元素不可改变,元素类型不能是任意的,"""​定义:t1=(11,22,33,44)#数据类型转......
  • 如何将多张CAD图纸合并成一个图纸文件?
    在CAD设计过程中,有些时候会需要将多张CAD图纸合并成一个图纸文件,可有些新手设计师对此并不了解,所以接下来的CAD教程小编将会以浩辰CAD软件为例来给大家分享一下将多张CAD图......
  • 列表(list)内置方法补充、字典(dict)内置方法、元组(tuple)内置方法、集合(set)内置方
    目录一、列表(list)内置方法补充二、字典(dict)内置方法三、元组(tuple)内置方法四、集合(set)内置方法一、列表(list)内置方法补充#reverse()颠倒列表内元素顺序#so......
  • pandas数据合并之concat
    数据合并concat#concat函数#参数解释concat(objs:Iterable[NDFrame]|Mapping[HashableT,NDFrame],axis:Axis=0,join:str="outer",#设置函数......
  • 数据类型-集合set-内置方法
    作用集合、list、tuple、dict一样都可以存放多个值,但是集合主要用于:去重、关系运算定义在{}内用逗号分隔开多个元素,集合具备以下三个特点:1:每个元素必须是不可变类......
  • Acwing 100.增减序列
    题目https://www.acwing.com/problem/content/102/由于题意为每次加一或减一,所以不需要用高级的数据结构。首先是思考怎么能实现最小次数。题意描述的是差分的过程,因此......
  • git合并分支的两种方法
    方法一:merge操作1.将当前分支修改数据commit gitcommit-m"thisislocalbranchcommit" 2.将分支切换到主分支 gitcheckoutmaster3.拉取主分支的最新代码 ......