当前位置： 首页 > news >正文

L2-024 部落 #GPLT,并查集 C++

news 来源：原创 2025/8/29 5:35:35

文章目录

  • 题目解读
    • 输入格式
    • 输出格式
  • 思路
  • Ac Code
  • 参考

题目解读

我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。

输入格式

第一行给出一个正整数N（≤104），是已知小圈子的个数。
随后N行,每行按一下格式给出一个小圈子里的人:
K P[1] P[2] ⋯ P[K] 其中K是小圈子里的人数,P[i]（i=1,⋯,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过104 。
之后一行给出一个非负整数Q，随后Q行,每行给出一对儿被查询的人的编号

输出格式

首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。

思路

使用并查集,将每个圈子的第一个人作为父节点,在合并集合的过程当中,统计人的个数,最后根节点的个数就是圈子的个数,而查询是否属于同一个圈子是并查集的基本应用

Ac Code

#include<bits/stdc++.h>using namespace std;//最多这么多人 
const int N = 1e4+10;
int f[N];//先写并查集板子
int find(int u){if(f[u]!=u)f[u]=find(f[u]);return f[u];
} void merge(int a,int b){int aa=find(a),bb =find(b);if(aa!=bb)f[aa]=bb;
}bool judge(int a,int b){return find(a)==find(b);
}int main(){int n;cin >> n;map<int,bool> mp;//存储状态 for(int i=0; i<N; i++)f[i]=i;for(int i=0; i<n; i++){int k;cin >> k;int fa;for(int j=0; j<k; j++){if(j==0){cin>>fa;if(mp.count(fa)==0)mp[fa]=1;}else{int x;cin >> x;if(mp.count(x)==0)mp[x]=1;merge(x,fa);}} }cout<<mp.size()<<" ";int res=0;for(int i=0; i<N; i++){//这个人需要先存在 if(mp.count(i) != 0 && f[i]==i)res++;} cout<<res<<endl;int q;cin >> q;while(q--){int a,b;cin >> a >> b;if(judge(a,b))cout<<"Y";else cout<<"N";cout << endl;} return 0;
}

参考

B站up主,一天能吃五顿饭

🌻编写本篇文章目的是笔者想以输出的形式进行学习，顺便记录学习点滴🌻

🌹 如果本篇文章对你有帮助的话那就点个赞吧👍🌹

😇 本篇文章可能存在多处不足，如有修改意见，可以私信或者评论我哦 😇

在这里插入图片描述

相关文章：

L2-024 部落 #GPLT,并查集 C++

文章目录 题目解读输入格式输出格式 思路Ac Code参考 题目解读 我们认为朋友的朋友都算在一个部落里&#xff0c;于是要请你统计一下&#xff0c;在一个给定社区中&#xff0c;到底有多少个互不相交的部落&#xff1f;并且检查任意两个人是否属于同一个部落。 输入格式 第一…...

编程日记 2025/8/29 5:35:35

【BFS最小步数】魔板题解

魔板题解 题目传送门 题目传送门 一、题目描述 Rubik先生发明了魔板的二维版本&#xff0c;这是一个有8个格子的板子&#xff0c;初始状态为&#xff1a; 1 2 3 4 8 7 6 5我们可以用三种操作来改变魔板状态&#xff1a; A&#xff1a;交换上下两行B&#xff1a;将最右边一…...

编程日记 2025/8/27 12:19:04

Qt之QHostInfo

简介 QHostInfo表示主机信息&#xff0c;即主机名称 常用接口 static QHostInfo fromName(const QString &name); QString hostName() const; QList<QHostAddress> addresses() const;结构 #mermaid-svg-HTJ95sEk8JwO4uCy {font-family:"trebuchet ms",…...

编程日记 2025/8/26 8:19:35

C++11观察者模式示例

该示例代码采用C11标准&#xff0c;解决以下问题&#xff1a; 消除了类继承的强耦合方式&#xff1b;通知接口使用可变参数模板&#xff0c;支持任意参数&#xff1b; 示例代码 .h文件如下&#xff1a; #include <functional> #include <string> #include <…...

编程日记 2025/8/29 5:33:41

解释观察者模式，如何实现观察者模式？

一、模式本质 观察者模式&#xff08;Observer Pattern&#xff09;建立​​对象间的一对多依赖关系​​&#xff0c;当核心对象&#xff08;Subject&#xff09;状态变化时&#xff0c;自动通知所有订阅者&#xff08;Observers&#xff09;。 这是一种​​推模型​​的典型…...

编程日记 2025/8/28 22:09:21

机器学习算法能够自动学习并使用不同条件下的变化趋势，确保预测结果的准确性的智慧地产开源了

智慧地产视觉监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒&#xff0c;省去繁琐重复的适配流程&#xff0c;实现芯片、算法、应用的全流程组合&#xff0c;从而大大减少企业级应用约95%的开发成本。 AI是新形势下数…...

编程日记 2025/8/26 19:35:52

【首款ARMv9开源芯片“星睿“O6测评】在“周易”NPU上部署Yolov8l模型并实现实时目标检测

博主未授权任何人或组织机构转载博主任何原创文章&#xff0c;感谢各位对原创的支持&#xff01; 博主链接 博客内容主要围绕&#xff1a; 5G/6G协议讲解 高级C语言讲解 Rust语言讲解 文章目录 在"星睿"O6的“周易”NPU上部署Yolov8l模型并实现…...

编程日记 2025/8/28 23:33:10

[ctfshow web入门] web4

前置知识 robots.txt是机器人协议&#xff0c;在使用爬虫爬取网站内容时应该遵循的协议。协议并不能阻止爬虫爬取&#xff0c;更像是一种道德规范。 假设robots.txt中写道 Disallow: /admind.php&#xff0c;那我就暴露了自己的后台&#xff0c;这属于信息泄漏&#xff0c;攻击…...

编程日记 2025/8/27 13:02:52

Golang的Goroutine（协程）与runtime

目录 Runtime 包概述 Runtime 包常用函数 1. GOMAXPROCS 2. Caller 和 Callers 3. BlockProfile 和 Stack 理解Golang的Goroutine Goroutine的基本概念 特点&#xff1a; Goroutine的创建与启动 示例代码 解释 Goroutine的调度 Gosched的作用 示例代码 输出 解…...

编程日记 2025/8/26 1:10:49

与Linux操作系统相关的引导和服务

目录 一.Linux操作系统引导过程 1.1引导过程总览 1.2系统初始化进程 1.2.1init进程 1.2.2sysmted 1.3systemd单元类型 二.排除启动类故障 2.1MBR扇区故障 2.1.1故障原因 2.1.2故障现象 2.1.3解决办法 2.1.4模拟修复MBR扇区故障 1)添加新的硬盘 2&#xff09;进行…...

编程日记 2025/8/28 7:46:34

JS API 事件监听

焦点事件案例&#xff1a;搜索框激活下拉菜单 事件对象 事件对象存储事件触发时的相关信息 可以判断用户按键&#xff0c;点击元素等内容 如何获取 事件绑定的回调函数中的第一个形参就是事件对象 一般命名为e,event 事件对象常用属性 type类型 click mouseenter client…...

编程日记 2025/8/23 18:58:47

【8】搭建k8s集群系列（二进制部署）之安装node节点组件（kubelet）

一、下载k8s二进制文件 下载地址&#xff1a; https://github.com/kubernetes/kubernetes/blob/master/CHANGELOG/CHANGELOG -1.20.md 注&#xff1a;打开链接你会发现里面有很多包&#xff0c;下载一个 server 包就够了&#xff0c;包含了 Master 和 Worker Node 二进制文件。…...

编程日记 2025/8/29 5:34:19

Harmony OS“一多” 详解：基于窗口变化的断点自适应实现

一、一多开发核心概念&#xff08;18N模式&#xff09; 目标&#xff1a;一次开发多端部署 解决的问题&#xff1a; 1、界面级一多&#xff1a;适配不同屏幕尺寸 2、功能级一多&#xff1a;设备功能兼容性处理(CanIUser) 3、工…...

编程日记 2025/8/27 15:58:40

Rust切片、结构体、枚举

文章目录 切片类型字符串切片其他结构的切片 结构体结构体实例元组结构体结构体所有权输出结构体结构体的方法结构体关联函数单元结构体 枚举match语法Option枚举类if let 语句 切片类型 切片&#xff08;Slice&#xff09;是对数据值的部分“引用” 我们可以从一个数据集合中…...

编程日记 2025/8/27 4:05:19

量子纠错码实战：从Shor码到表面码

引言&#xff1a;量子纠错的必要性 量子比特的脆弱性导致其易受退相干和噪声影响&#xff0c;单量子门错误率通常在10⁻~10⁻量级。量子纠错码&#xff08;QEC&#xff09;通过冗余编码测量校正的机制&#xff0c;将逻辑量子比特的错误率降低到可容忍水平。本文从首个量子纠错…...

编程日记 2025/8/28 1:12:47

Pod的生命周期

概念 Pod对象自从其创建开始至其终止退出的时间范围称为其生命周期。在这段时间中&#xff0c;Pod会处于多种不同的状态&#xff0c;并执行一些操作&#xff1b;其中&#xff0c;创建主容器&#xff08;main container&#xff09;为必需的操作&#xff0c;其他可选的操作还包…...

编程日记 2025/8/29 0:19:24

使用QAction编辑器添加QAction到ui里

在 Qt Designer 或 Qt Creator 的 UI 设计器 中&#xff0c;可以直接通过 Action Editor 可视化添加和管理 QAction&#xff0c;无需手动编写代码。以下是详细步骤&#xff1a; 步骤 1&#xff1a;打开 Action Editor 在 Qt Creator 中打开 .ui 文件&#xff08;双击项目中的…...

编程日记 2025/8/27 21:29:44

Unity：标签（tags）

为什么需要Tags&#xff1f; 在游戏开发中&#xff0c;游戏对象&#xff08;GameObject&#xff09;数量可能非常多&#xff0c;比如玩家、敌人、子弹等。开发者需要一种简单的方法来区分这些对象&#xff0c;并根据它们的类型执行不同的逻辑。 核心需求&#xff1a; 分类和管…...

编程日记 2025/8/29 2:57:19

深入解析 Python 正则表达式：全面指南与实战示例

深入解析 Python 正则表达式&#xff1a;全面指南与实战示例 &#x1f4cc; 引言 正则表达式&#xff08;Regular Expressions, regex&#xff09;是用于文本匹配、查找和替换的强大工具。在 Python 中&#xff0c;我们可以使用 re 模块来处理正则表达式。无论是数据清洗、日…...

编程日记 2025/8/28 13:40:25

Nginx介绍及使用

1.Nginx介绍 Nginx是一款开源的、高性能的HTTP和反向代理服务器 1.正向代理和反向代理 正向代理&#xff08;代理客户端&#xff09;是一种位于客户端和目标服务器之间的中间服务器。客户端通过正向代理服务器向目标服务器发送请求&#xff0c;代理服务器将请求转发给目标服…...

编程日记 2025/8/27 15:12:45

【Block总结】自适应矩形卷积，即插即用|CVPR2025

论文信息 标题: Adaptive Rectangular Convolution for Remote Sensing Pansharpening年份: 2025年会议: CVPR论文地址: arXiv代码地址: GitHub任务: 遥感图像融合&#xff08;Pansharpening&#xff09; 创新点 本论文提出了一种新颖的自适应矩形卷积模块&#xff08;ARCon…...

编程日记 2025/8/28 7:44:13

第2课：JSX语法与组件基础

第2课&#xff1a;JSX语法与组件基础 学习目标 深入理解JSX语法掌握组件的基本结构和用法学习使用Props传递数据掌握React中的样式添加方法创建任务卡片组件 一、JSX语法深入 1. 什么是JSX&#xff1f; JSX是JavaScript XML的缩写&#xff0c;它允许我们在JavaScript中编写…...

编程日记 2025/8/27 21:55:27

DevOps与Docker的关系

DevOps 与 Docker 是相辅相成的关系。DevOps 是一种强调开发&#xff08;Development&#xff09;与运维&#xff08;Operations&#xff09;之间协作的文化、实践和工具链&#xff0c;而 Docker 是一种容器化技术&#xff0c;为 DevOps 的实现提供了高效的技术支撑。 Docker …...

编程日记 2025/8/27 3:45:12

嵌入式AI简介

嵌入式AI是一种将人工智能算法部署在终端设备中运行的技术&#xff0c;使智能硬件能够在本地实时完成感知、交互和决策功能&#xff0c;无需依赖云端计算。以下是其核心要点&#xff1a; 一、核心特点 1. 本地化处理&#xff1a;数据在设备端直接处理&#xff0c;无需联网&a…...

编程日记 2025/8/28 12:44:28

多GPU训练

写在前面 限于财力不足&#xff0c;本机上只有一个 GPU 可供使用&#xff0c;因此这部分的代码只能够稍作了解&#xff0c;能够使用的 GPU 也只有一个。 多 GPU 的数据并行&#xff1a;有几张卡&#xff0c;对一个小批量数据&#xff0c;有几张卡就分成几块&#xff0c;每个 …...

编程日记 2025/8/28 1:13:01

JVM虚拟机篇（三）：JVM运行时数据区与方法区详解

JVM虚拟机篇&#xff08;三&#xff09;&#xff1a;JVM运行时数据区与方法区详解 JVM虚拟机篇&#xff08;三&#xff09;&#xff1a;JVM运行时数据区与方法区详解一、引言二、JVM运行时数据区2.1 概述2.2 各部分的作用与交互2.2.1 堆与其他区域的关系2.2.2 方法区与其他区域…...

编程日记 2025/8/27 9:45:26

Rust学习日记：编写一个Python扩展

参考https://segmentfault.com/a/1190000044555330 命令行创建一个新的Rust项目cargo new --lib rust_python_ext 配置Cargo.toml [package] name "rust_python_ext" version "0.1.0" edition "2024"[lib] name "rust_python_ext"…...

编程日记 2025/8/28 13:23:29

Pod的调度

在默认情况下&#xff0c;一个Pod在哪个Node节点上运行&#xff0c;是由Scheduler组件采用相应的算法计算出来的&#xff0c;这个过程是不受人工控制的。但是在实际使用中&#xff0c;这并不满足的需求&#xff0c;因为很多情况下&#xff0c;我们想控制某些Pod到达某些节点上&…...

编程日记 2025/8/28 7:07:50

系统思考：思考的快与慢

在做重大决策之前&#xff0c;什么原因一定要补充碳水化合物&#xff1f;人类的大脑其实有两套运作模式&#xff1a;系统1&#xff1a;自动驾驶模式&#xff0c;依赖直觉&#xff0c;反应快但易出错&#xff1b;系统2&#xff1a;手动驾驶模式&#xff0c;理性严谨&#xff0c;…...

编程日记 2025/8/27 16:50:51

[ 计算机网络 ] | HTTP协议(一)

目录 前置知识&#xff1a; URL URL的URLENCODE和URLDECODE HTTP协议的宏观格式 如何保证报文是完整的&#xff1f;怎么做序列&#xff0c;反序列化的&#xff1f; 前置知识&#xff1a; URL 我们把数据给别人&#xff0c;别人把数据给我们&#xff0c;不是在做IO嘛~&am…...

编程日记 2025/8/27 7:25:24

大模型快速 ASGI 服务器uvicorn

基础概念类 1. 什么是 Uvicorn&#xff0c;它的作用是什么&#xff1f; 答案&#xff1a;Uvicorn 是一个基于 Python 的快速 ASGI&#xff08;异步服务器网关接口&#xff09;服务器。它的主要作用是作为 Web 应用程序的服务器&#xff0c;负责接收客户端的请求&#xff0c;并…...

编程日记 2025/8/28 19:20:44

android studio 基础

1.android Module not specified 今天做一个实验时出现&#xff1a;Android Studio Run/Debug configuration error: Module not specified&#xff0c;要想解决这个问题&#xff1a; 1、打开根目录的 settings.gradle&#xff0c;删除 include :exampleapp 2、在 Android Stu…...

编程日记 2025/8/28 3:03:11

python爬虫爬取淘宝热销(热门)零食商品加数据清洗、销量、店铺及词云数据分析_源码及相关说明文档；售后可私博主

TOC 如有侵权,联系删除 一、环境说明 使用前必须检查以下环境 &#xff08;1&#xff09;python编译环境 &#xff08;2&#xff09;python脚本执行所需要的库&#xff0c;具体看代码&#xff08;main.py&#xff09;import导入的部分库 &#xff08;3&#xff09;确保电脑可…...

编程日记 2025/8/26 23:49:13

Android /proc/meminfo解释

高通8295设备 msmnile_gvmq:/proc # cat meminfo MemTotal: 16433968 kB MemFree: 7709832 kB…...

编程日记 2025/8/27 18:05:02

VScode 玩 MCP的server

vscode 1.99版本刚支持MCP server&#xff0c;我就测试了一下 翻到一个gitte的MCP sever 我本身是Mac版本1.99居然没更新agent&#xff0c;所以我就直接用1.100版本的vscode inside了来掩饰一下了 点击setting&#xff0c;然后你要edit一下这个json配置文件 主要修改的其实是…...

编程日记 2025/8/28 4:08:24

详解 MySQL 索引的最左前缀匹配原则

MySQL 的最左前缀匹配原则主要是针对复合索引&#xff08;也称为联合索引&#xff09;而言的。其核心思想是&#xff1a;只有查询条件中包含索引最左侧&#xff08;第一列&#xff09;开始的连续一段列&#xff0c;才能让 MySQL 有效地利用该索引。 一、 复合索引的结构 复合…...

编程日记 2025/8/28 10:15:26

ROS Master多设备连接

Bash Shell Shell是位于用户与操作系统内核之间的桥梁&#xff0c;当用户在终端敲入命令后&#xff0c;这些输入首先会进入内核中的tty子系统&#xff0c;TTY子系统负责捕获并处理终端的输入输出流&#xff0c;确保数据正确无误的在终端和系统内核之中。Shell在此过程不仅仅是…...

编程日记 2025/8/27 20:35:33

【Mysql】数据库备份与恢复

一、备份类型 物理备份&#xff1a;直接对数据库的数据文件、日志文件、索引文件进行备份 逻辑备份&#xff1a;对数据库对象&#xff08;库、表&#xff09;以SQL语句的形式导出进行备份 二、备份工具 1、使用tar、gzip等方式压缩打包数据库文件&#xff08;完全备份、物理冷…...

编程日记 2025/8/28 11:21:21

Java HttpURLConnection修仙指南：从萌新到HTTP请求大能的渡劫手册

一、筑基篇&#xff1a;初识HttpURLConnection 1.1 基础开光&#xff08;创建连接&#xff09; URL url new URL("https://api.example.com/data"); HttpURLConnection conn (HttpURLConnection) url.openConnection(); // 注意&#xff01;此处可能抛出Malforme…...

编程日记 2025/8/24 16:58:12

python 重要易忘 语言基础

Collections 1、Counter 计数器 counter:计数器 类似字典 统计可迭代对象中元素的出现次数, Counter({b: 3, c: 2, a: 1, d: 1}) 相当于字典{b: 3, c: 2, a: 1, d: 1} a.items() 取键值对 对应为dict_items([(a, 1), (b, 3), (c, 2), (d, 1)]) 也可以是 list(a.items…...

编程日记 2025/8/27 10:34:20

【新能源汽车研发测试数据深度分析：从传感器到智能决策的硬核方法论】

摘要&#xff1a; 本文系统性解构新能源汽车&#xff08;NEV&#xff09;研发测试中的数据采集、处理及分析全链条&#xff0c;覆盖传感器融合、大数据清洗、AI算法优化等核心技术&#xff0c;并引入行业顶级案例&#xff08;如特斯拉Autopilot验证、宁德时代BMS算法迭代&#…...

编程日记 2025/8/27 12:56:56

GD32H759IMT6 Cortex-M7 OpenHarmony轻量系统移植——接管中断修改为不接管

笔者在去年利用国庆时间&#xff0c;将Cortex-M7 的国产厂商兆易创新GD32H459移植OpenHarmony轻量系统&#xff0c;但是适配不太完善——只能选择liteos-m接管中断。这样导致使用中断非常麻烦。于是笔者最近将接管中断模式修改为不接管&#xff0c;这样可以方便的使用gd32提供的…...

编程日记 2025/8/26 13:01:51

MySQL基础学习笔记

学习笔记 1. 基础小知识1.1 数据库分类1.2 下载安装、变量配置过程&#xff08;略&#xff09;1.3 连接命令1.4 连接mysql服务端的软件选择1.4.1 要求不高的话&#xff0c;选择有很多1.4.2 适合做企业级管理的工具&#xff08;适合团队协作&#xff09;1.4.3 总结 1.5 编程语言…...

编程日记 2025/8/26 1:32:12

[Linux]进程状态、僵尸进程处理回收、进程优先级 + 图例展示

目录 一、进程状态 1.一般操作系统学科的进程状态 二、Linux操作系统的进程状态 运行状态&#xff08;R&#xff09; 睡眠状态&#xff08;S&#xff09; 深度睡眠状态&#xff08;D&#xff09; 暂停状态&#xff08;T&#xff09; 追踪暂停状态&#x…...

编程日记 2025/8/28 0:27:16

2022 年 6 月青少年软编等考 C 语言七级真题解析

目录 T1. 有多少种二叉树思路分析T2. 城堡问题T3. 快速堆猪思路分析T4. 重建二叉树思路分析T1. 有多少种二叉树 题目链接：SOJ D1189 输入 n ( 1 < n < 13 ) n\ (1<n<13) n (1<n<13)，求 n n n 个结点的二叉树有多少种形态？ 思路分析 此题考查 C a…...

编程日记 2025/8/28 9:42:15

flutter修改 Container 中的 Text 和 Image 的样式

在Flutter中&#xff0c;Container 是一个常用的布局组件&#xff0c;它可以包含子组件&#xff08;如文本、图片等&#xff09;&#xff0c;并允许你通过设置各种属性来自定义样式。如果你需要修改 Container 中的 Text 和 Image 的样式&#xff0c;可以通过以下方式实现。 1.…...

编程日记 2025/8/28 10:01:04

零基础入门unity游戏开发——动画篇】Animation动画窗口，创建编辑动画

考虑到每个人基础可能不一样&#xff0c;且并不是所有人都有同时做2D、3D开发的需求&#xff0c;所以我把 【零基础入门unity游戏开发】 分为成了C#篇、unity通用篇、unity3D篇、unity2D篇。 【C#篇】&#xff1a;主要讲解C#的基础语法&#xff0c;包括变量、数据类型、运算符、…...

编程日记 2025/8/27 6:09:45

【设计模式】命令模式

简介 假设你有一个智能家居遥控器&#xff0c;上面有多个按钮&#xff0c;每个按钮对应不同的设备操作&#xff08;如开灯、关灯、调空调温度&#xff09;。 命令模式的解决方案是&#xff1a; 将每个操作&#xff08;如“开灯”&#xff09;封装成一个独立的命令对象&#x…...

编程日记 2025/8/28 10:07:45

Python作业3 字符田字格绘制

字符田字格绘制&#xff1a;编写程序,用字符方式打印输出一个简单的田字格,要求采用函数方式,以田字格宽度为参数,能够根据参数绘制任意大小的田字格。 def draw(n):line 3 * n 1for i in range(1, line 1):if i % 3 1:print(n * " —— —— ", end"&quo…...

编程日记 2025/8/28 1:57:32

文章记单词 | 第23篇（六级）

一&#xff0c;单词释义 occupy /ˈɒkjupaɪ/v. 占用&#xff0c;占领&#xff0c;使忙碌thermal /ˈθɜːml/adj. 热的&#xff0c;热量的&#xff0c;保暖的&#xff1b;n. 热气流persistent /pəˈsɪstənt/adj. 执着的&#xff0c;坚持不懈的&#xff0c;持续存在的wee…...

编程日记 2025/8/28 6:16:48