字节9.3秋招研发笔试 【后端方向】第三题
题目
小红拿到了一个无向图,初始每人节点是白色,其中有若干个节点被染成了红色。小红想知道,若将 i 号节点染成红色,当前的红色连块的数量是多少? 你需要回答i∈[1,n] 的答案。
定义,若干节点组成一个红色连通块,当且仅当它们都是红色节点,且在该图上可以通过无向边互相到达,这些可以连通的节点构成的最大集合为一个连通块。
代码
考察:并查集,建图
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/*保存所有边当边的两端节点都为红色,合并连通块遍历节点:若为红,输出当前连通块数量all;若为白,遍历其连接的红节点,得出其连接的连通块数量x,cnt_i = all - x + 1
*/
vector<vector<bool>> edges;
string colors; // 记录颜色
int cnt= 0; // 连通块数量
class UnionFind {vector<int> parents;
public:UnionFind(int n) {parents.resize(n + 1);for(int i = 1; i <= n; i++) {parents[i] = i;}}void Union(int x, int y) {int fx = find(x);int fy = find(y);if(fx != fy) {parents[fy] = fx;}return;}int find(int x) {if(parents[x] != x) {parents[x] = find(parents[x]);}return parents[x];}int cnt_red() {int num = 0;for(int i = 1; i < parents.size(); i++) {if(parents[i] == i && colors[i - 1] == 'R')num++;}return num;}
};int main() {int n, m;cin >> n >> m;UnionFind* uf = new UnionFind(n);cin >> colors;edges.resize(n + 1);for(int i = 1; i <= n; i++) {edges[i].resize(n + 1);}int u, v;for(int i = 0; i < m; i++) {cin >> u >> v;edges[u][v] = true;edges[v][u] = true;if(colors[u - 1] == 'R' && colors[v - 1] == 'R') {uf->Union(u, v);}}cnt = uf->cnt_red();/*遍历节点:若为红,输出当前连通块数量all;若为白,遍历其连接的红节点,得出其连接的连通块数量x,cnt_i = all - x + 1*/for(int i = 1; i <= n; i++) {if(colors[i - 1] == 'R') {cout << cnt;}else {unordered_set<int>st; // 存储i点连接的连通块for(int j = 1; j <= n; j++) {if(edges[i][j] == true && colors[j - 1] == 'R'){st.insert(uf->find(j));}}cout << cnt - st.size() + 1;}if(i != n) cout << endl;}return 0;
}
/*
4 4
WRWR
1 2
2 3
3 4
1 41
2
1
2
*/
相关文章:
字节9.3秋招研发笔试 【后端方向】第三题
题目 小红拿到了一个无向图,初始每人节点是白色,其中有若干个节点被染成了红色。小红想知道,若将 i 号节点染成红色,当前的红色连块的数量是多少? 你需要回答i∈[1,n] 的答案。 定义,若干节点组成一个红色连通块&am…...

Solidity 小白教程:8. 变量初始值
Solidity 小白教程:8. 变量初始值 变量初始值 在solidity中,声明但没赋值的变量都有它的初始值或默认值。这一讲,我们将介绍常用变量的初始值。 值类型初始值 boolean: falsestring: “”int: 0uint: 0enum: 枚举中的第一个元素address: …...

时序预测 | MATLAB实现EEMD-SSA-LSTM、EEMD-LSTM、SSA-LSTM、LSTM时间序列预测对比
时序预测 | MATLAB实现EEMD-SSA-LSTM、EEMD-LSTM、SSA-LSTM、LSTM时间序列预测对比 目录 时序预测 | MATLAB实现EEMD-SSA-LSTM、EEMD-LSTM、SSA-LSTM、LSTM时间序列预测对比预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 时序预测 | MATLAB实现EEMD-SSA-LSTM、E…...

京东搜索EE链路演进 | 京东云技术团队
导读 搜索系统中容易存在头部效应,中长尾的优质商品较难获得充分的展示机会,如何破除系统的马太效应,提升展示结果的丰富性与多样性,助力中长尾商品成长是电商平台搜索系统的一个重要课题。其中,搜索EE系统在保持排序…...

【C++】反向迭代器精讲(以lIst为例)
目录 二,全部代码 三,设计思路 1. 讨论 2. 关于迭代器文档一个小细节 结语 一,前言 如果有小伙伴还未学习普通迭代器,请参考这篇文章中的普通迭代器实现。 【STL】list用法&试做_底层实现_花果山~~程序猿的博客-CSDN…...

时序预测 | MATLAB实现基于PSO-GRU、GRU时间序列预测对比
时序预测 | MATLAB实现基于PSO-GRU、GRU时间序列预测对比 目录 时序预测 | MATLAB实现基于PSO-GRU、GRU时间序列预测对比效果一览基本描述程序设计参考资料 效果一览 基本描述 MATLAB实现基于PSO-GRU、GRU时间序列预测对比。 1.MATLAB实现基于PSO-GRU、GRU时间序列预测对比&…...

2023年高教社杯 国赛数学建模思路 - 案例:感知机原理剖析及实现
文章目录 1 感知机的直观理解2 感知机的数学角度3 代码实现 4 建模资料 # 0 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 1 感知机的直观理解 感知机应该属于机器学习算法中最简单的一种算法,其…...
Java 利用pdfbox将图片和成到pdf指定位置
业务背景:用户在手机APP上进行签名,前端将签完名字的图片传入后端,后端合成新的pdf. 废话不多说,上代码: //控制层代码PostMapping("/imageToPdf")public Result imageToPdf(RequestParam("linkName&…...
大数据课程K19——Spark的电影推荐案例推荐系统的冷启动问题
文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 掌握Spark的案例——电影推荐; ⚪ 掌握Spark的模型存储; ⚪ 掌握Spark的模型加载; ⚪ 掌握Spark的推荐系统的冷启动问题; 一、案例——电影推荐 1. 基于用户的推荐 1. 说明 我们现…...

Docker-安装(Linux,Windows)
目录 前言安装版本Docker版本说明前提条件Linux安装使用YUM源部署获取阿里云开源镜像站YUM源文件安装Docker-ce配置Docker Daemon启动文件启动Docker服务并查看已安装版本 使用二进制文件部署 Windows安装实现原理安装步骤基本使用 参考说明 前言 本文主要说明Docker及其相关组…...

若依富文本 html样式 被过滤问题
一.场景 进入页面,富文本编辑框里回显这条新闻内容,如下图, 然后可以在富文本编辑框里对它实现再编辑,编辑之后将html代码提交保存到后台数据库。可以点击详情页进行查看。 出现问题:在提交到后台controller时&#x…...
VS Code 快速消除前置空格和常用快捷键
目录 介绍: 消除前置空格:SHIFTTAB 常用的 VS Code 快捷键 介绍: 在使用 Visual Studio Code (VS Code) 进行代码编辑时,熟练掌握一些快捷键和编辑技巧可以大幅提高开发效率。本文将重点介绍如何使用快捷键 SHIFTTAB 快速消除代…...
【跟小嘉学 Rust 编程】二十五、Rust命令行参数解析库(clap)
系列文章目录 【跟小嘉学 Rust 编程】一、Rust 编程基础 【跟小嘉学 Rust 编程】二、Rust 包管理工具使用 【跟小嘉学 Rust 编程】三、Rust 的基本程序概念 【跟小嘉学 Rust 编程】四、理解 Rust 的所有权概念 【跟小嘉学 Rust 编程】五、使用结构体关联结构化数据 【跟小嘉学…...

gRPC远程进程调用
gRPC远程进程调用 rpc简介golang实现rpc方法一net/rpc库golang实现rpc方法二jsonrpc库grpc和protobuf在一起第一个grpc应用grpc服务的定义和服务的种类grpc stream实例1-服务端单向流grpc stream实例2-客户端单向流grpc stream实例3-双向流grpc整合gin...

什么是继承
提示:继承基础概念 文章目录 一、继承1.1 基础概念1.2 继承作用与继承方式1.2 继承中的隐藏1.3 类中构造、析构在继承方面知识1.4 继承知识拓展 一、继承 1.1 基础概念 继承机制是面向对象程序设计使代码可以复用的最重要的手段,它允许在保持原有类特性…...

QT连接数据库
目录 数据库 数据库基本概念 常用的数据库 SQLite3基础 SQLite特性: QT连接数据库 1.1 QT将数据库分为三个层次 1.2 实现数据库操作的相关方法 sql语句(常用) 1)创建表格 2)删除表格 3)插入记录 …...

navicat访问orcal数据库
1)因为不能直接访问服务器,所以通过中介进行了端口转发; 2)依然不能访问,提示netadmin权限什么错误; 3)下载了一个 PLSQL Developer 13.0.0.1883 版本,自带的instantclient 好像不…...
Linux中查找某路径下,包含某个字符串的所有文件
path表示需要查找的路径,string表示需要包含的字符\字符串 grep -rnw path -e "string"只查找包含特定string的所有.c和.h文件 grep --include\*.{c,h} -rnw -rnw path -e "string" 除去所有.o文件,查找其他文件是否包含特定strin…...
常见信号滤波方法(卡尔曼滤波、滑动平均、异常值剔除)的原理解析与C语言实现
常见信号滤波方法(卡尔曼滤波、滑动平均、异常值剔除)的原理解析与C语言实现 日期作者版本备注2023.09.04Dog TaoV1.0完成文档的初始版本。 文章目录 常见信号滤波方法(卡尔曼滤波、滑动平均、异常值剔除)的原理解析与C语言实现前…...

WebGL模型矩阵
前言:依赖矩阵库 WebGL矩阵变换库_山楂树の的博客-CSDN博客 先平移,后旋转的模型变换: 1.将三角形沿着X轴平移一段距离。 2.在此基础上,旋转三角形。 先写下第1条(平移操作)中的坐标方程式。 等式1&am…...

接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...

centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...

2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...

MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...