代码编织梦想

文章目录

Question

给定一个包含 n
个点(编号为 1∼n
)的无向图,初始时图中没有边。

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

C a b,在点 a
和点 b
之间连一条边,a
和 b
可能相等;
Q1 a b,询问点 a
和点 b
是否在同一个连通块中,a
和 b
可能相等;
Q2 a,询问点 a
所在连通块中点的数量;
输入格式
第一行输入整数 n
和 m

接下来 m
行,每行包含一个操作指令,指令为 C a b,Q1 a b 或 Q2 a 中的一种。

输出格式
对于每个询问指令 Q1 a b,如果 a
和 b
在同一个连通块中,则输出 Yes,否则输出 No。

对于每个询问指令 Q2 a,输出一个整数表示点 a
所在连通块中点的数量

每个结果占一行。

数据范围
1≤n,m≤105
输入样例:
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例:
Yes
2
3

Ideas

并查集应用

Code

#include <iostream>

using namespace std;
const int N = 1e5 + 10;
int p[N]; // 存储的是每个节点的父节点
int cnt[N]; // 每个集合的元素个数,只统计根节点

// 返回x的根节点 + 路径压缩
int find(int x)
{
    if (p[x] != 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;
        cnt[i] = 1;
    }
    
    
    while(m --)
    {
        char op[5];
        int a, b;
        scanf("%s", op);
        if (op[0] == 'C')
        {
            scanf("%d%d", &a, &b);
            if (find(a) == find(b)) continue; 
            cnt[find(b)] += cnt[find(a)]; // 将a集合的元素数量加到b集合上
            p[find(a)] = find(b); // 将a集合合并到b集合上
        }
        else if(op[1] == '1')
        {
            scanf("%d%d", &a, &b);
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else
        {
            scanf("%d", &a);
            printf("%d\n", cnt[find(a)]);
        }
    } 
    
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_49821869/article/details/128859365

AcWing 837. 连通块中点的数量(并查集)-爱代码爱编程

给定一个包含n个点(编号为1~n)的无向图,初始时图中没有边。 现在要进行m个操作,操作共有三种: “C a b”,在点a和点b之间连一条边,a和b可能相等;“Q1 a b”,询问点a和点b是否在同一个连通块中,a和b可能相等;“Q2 a”,询问点a所在连通块中点的数量;输入格式 第一行输入整数n和m。 接下来m行,每行包含一个操作指令,指令为“C

837. 连通块中点的数量(并查集)-爱代码爱编程

给定一个包含n个点(编号为1~n)的无向图,初始时图中没有边。 现在要进行m个操作,操作共有三种: “C a b”,在点a和点b之间连一条边,a和b可能相等; “Q1 a b”,询问点a和点b是否在同一个连通块中,a和b可能相等; “Q2 a”,询问点a所在连通块中点的数量;输入格式 第一行输入整数n和m。 接下来m行,每行包含一个操作指令,指令为“

AcWing 837. 连通块中点的数量(C++)-爱代码爱编程

837. 连通块中点的数量 分析 这题是并查集的典型应用,并查集可以用来维护无向图的连通块 这题的三种操作可以这样理解: 1.要求把两个点连起来,本质是把这两个点放到同一个集合中 2.查询两个点是否在同一个集合中,本质是找这两个点所在集合的根节点是否相等 3.查询某个点所在的集合的点的总数量 因为这题有些操作是重复使用的,所以需要把功能独立出来,也

【ACWing】837. 连通块中点的数量-爱代码爱编程

题目地址: https://www.acwing.com/problem/content/839/ 给定一个包含 n n n个点(编号为

AcWing 837. 连通块中点的数量【并查集】-爱代码爱编程

AcWing 837. 连通块中点的数量 一、题目链接二、题目分析(一)算法标签(二)解题思路三、AC代码四、其它题解 一、题目链接 AcWing 837. 连通块中点的数量 二、题目分析 (一)算法标签 并查集 (二)解题思路 注意本题输入操作不要用char op[3]; + scanf("%s", op); 要用string o

AcWing 837. 连通块中点的数量(并查集)-爱代码爱编程

#include<bits/stdc++.h> using namespace std; const int N=100010; int p[N],sizee[N]; int findd(int x){//路径压缩 if(p[x]!=x){ p[x]=findd(p[x]); } return p[x]; } int main(

AcWing 837. 连通块中点的数量(自己整理)-爱代码爱编程

837. 连通块中点的数量​​​​​ 给定一个包含 nn 个点(编号为 1∼n1∼n)的无向图,初始时图中没有边。 现在要进行 mm 个操作,操作共有三种: C a b,在点 aa 和点 bb 之间连一条边,aa 和 bb 可能相等;Q1 a b,询问点 aa 和点 bb 是否在同一个连通块中,aa 和 bb 可能相等;Q2 a,询问点 aa 所在连

acwing 837. 连通块中点的数量_麻辣姐没辣椒的博客-爱代码爱编程

Acwing 837. 连通块中点的数量 题目描述 给定一个包含 n 个点(编号为 1∼n)的无向图,初始时图中没有边。 现在要进行 m 个操作,操作共有三种: C a b,在点 a和点 b 之间连一条边,a 和 b可能相等;Q1 a b,询问点 a和点 b 是否在同一个连通块中,a 和 b可能相等;Q2 a,询问点 a所在连通块中点的数量输入格式

acwing 837. 连通块中点的数量 (并查集维护额外信息---集合数量)__刘小雨的博客-爱代码爱编程

在上一节写了,并查集中,主要有两个功能,现在探索一下,并查集能不能保存额外的信息呢 回答是可以的哈 并查集保存额外的信息: 这里指的是保存每个集合的数量。 题目 给定一个包含 n 个点(编号为 1∼n)的无向图,初始时图中没有边。 现在要进行 m 个操作,操作共有三种: C a b,在点 a 和点 b 之间连一条边,a 和 b 可能相等; Q1

acwing 837. 连通块中点的数量(查并集)_消逝在长夜里.的博客-爱代码爱编程

题目描述: 给定一个包含 n个点(编号为 1∼n)的无向图,初始时图中没有边。 现在要进行 m 个操作,操作共有三种: C a b,在点 a 和点 b 之间连一条边,a 和 b 可能相等;Q1 a b,询问点 a 和点 b 是否在同一个连通块中,a 和 b 可能相等;Q2 a,询问点 a 所在连通块中点的数量;输入格式: 第一行输入整数 n 和 m

acwing 837. 连通块中点的数量-java_依嘫_吃代码的博客-爱代码爱编程

题目所属分类 维护size的并查集模板: int p[N], size[N]; //p[]存储每个点的祖宗节点, //size[]只有祖宗节点的有意义,表示祖宗节点所在集合中的点的数量

day25|51.n皇后、37.解数独-爱代码爱编程

51.N皇后 按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。 给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了

day52最长递增子序列-爱代码爱编程

力扣300.最长递增子序列 题目链接:https://leetcode.cn/problems/longest-increasing-subsequence/ 思路 dp数组的含义 dp[i]表示,以nums[i]结

leetcode 1071. greatest common divisor of strings(字符串的最大公约数)-爱代码爱编程

For two strings s and t, we say “t divides s” if and only if s = t + … + t (i.e., t is concatenated with itself

oj万题详解––卫星地图(c++详解)-爱代码爱编程

目录 题目 分析 参考代码 题目 题目描述 一张矩形的卫星地图,有M行N列。行列中的0表示空地,1表示有建筑。有3种类型的建筑: L型: 仅在一行上占据连续的若干个格子,长度至少为2,至多为N C型:仅在一列上占据连续的若干个格子,长度至少为2,至多为M S型:仅占据单个格子。 在同一行上或者同一列上可以出现多个

代码随想录算法训练营day53动态规划:1143.最长公共子序列,1035.不相交的线,53. 最大子序和-爱代码爱编程

要思考dp是由哪几个状态推导而来 1143.最长公共子序列 文章链接:代码随想录 (programmercarl.com) 思路:无思路 看完文章后的反思:与718.最长重复子数组的区别在于,此题不要求是连续的 (1)确定dp数组含义 dp[i][j]:长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的

tidb 6.5 新特性解析丨过去一年,我们是如何让 tiflash 高效又稳定地榨干 cpu?-爱代码爱编程

TiDB 6.5 LTS 版本已经发布了。这是 TiDB V6 的第二个长期支持版,携带了诸多备受期待的新特性:产品易用性进一步提升、内核不断打磨,更加成熟、多样化的灾备能力、加强应用开发者生态构建…… TiDB 6.5

​力扣解法汇总2325. 解密消息-爱代码爱编程

 目录链接: 力扣编程题-解法汇总_分享+记录-CSDN博客 GitHub同步刷题项目: https://github.com/September26/java-algorithms 原题链接:力扣 描述: 给你字符串 key 和 message ,分别表示一个加密密钥和一段加密消息。解密 message 的步骤如下: 使用 key