UVa247 Calling Circles(Floyd warshall算法)
题意
给定两个人相互打电话,如果a打给b,b打给c,c打给a,则说a,b,c在同一电话圈中。给出n个人的m次通话,输出所有的电话圈
思路
用graph[u][v]=1表示u和v之间有打电话。在使用floyd算法计算所有的点对之间的值。graph[u][v]=1表示u,v之间有直接或者间接打电话。如果graph[u][v] = 1并且graph[v][u]=1,说明u和v是在同一个电话圈
代码如下
#include <bits/stdc++.h>using namespace std;const int N = 30;#define _for(i, a, b) for(int i = (a); i < (b); i++)
#define _rep(i, a, b) for (int i = (a); i <= (b); i++)int n, m;
int graph[N][N];
bool vis[N];
map<string, int> nameMap;
vector<string> names;int getId(const string& name)
{if (!nameMap.count(name)){int size = names.size();nameMap[name] = size;names.push_back(name);}return nameMap[name];
}void fastio()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
}int main()
{fastio();#ifndef ONLINE_JUDGEifstream fin("f:\\OJ\\uva_in.txt");streambuf* back = cin.rdbuf(fin.rdbuf());#endifint kase = 1;while (cin >> n >> m) {if (n == 0 && m == 0) {break;}if (kase > 1) {cout << endl;}nameMap.clear();names.clear();memset(graph, 0, sizeof(graph));fill(vis, vis + N, false);_for(i, 0, m) {string a, b;cin >> a >> b;int u = getId(a);int v = getId(b);graph[u][v] = 1;}_for(k, 0, n) {_for(i, 0, n) {_for(j, 0, n) {graph[i][j] = graph[i][j] || (graph[i][k] && graph[k][j]);}}}cout << "Calling circles for data set " << kase << ":" << endl;_for(u, 0, n) {if (vis[u]) {continue;}vis[u] = true;cout << names[u];_for(v, 0, n) {if (!vis[v] && graph[u][v] && graph[v][u]) {vis[v] = true;cout << ", " << names[v];}}cout << endl;}kase++;}#ifndef ONLINE_JUDGEcin.rdbuf(back);#endifreturn 0;
}
相关文章:
UVa247 Calling Circles(Floyd warshall算法)
题意 给定两个人相互打电话,如果a打给b,b打给c,c打给a,则说a,b,c在同一电话圈中。给出n个人的m次通话,输出所有的电话圈 思路 用graph[u][v]1表示u和v之间有打电话。在使用floyd算法计算所有的点对之间的值。graph[u][v]1表示u,v之间有直接…...
Java项目之基于ssm框架的社区生活超市管理系统(附源码)
基于ssm框架的社区生活超市管理系统设计与实现(程序源码毕业论文) 大家好,今天给大家介绍基于ssm框架的社区生活超市管理系统设计与实现,本论文只截取部分文章重点,文章末尾附有本毕业设计完整源码及论文的获取方式。更…...
Android 实现录音功能
思路: 通过媒体录制器MediaRecorder实现:MediaRecorder是Android自带的音频和视频录制工具,它通过操纵摄像头和麦克风完成媒体录制,既可录制视频,又可单独录制音频。 MediaRecorder常用方法(录音与录像通用)…...
drawio导出矢量图
1.选中要导出的图 2.导出为pdf 3.用adobe打开pdf,另存为eps...
关于angular router-outlet
关于angular router-outlet Angular是一个现代化的前端框架,它提供了很多强大的工具来帮助我们开发出高效的Web应用。其中一个最常用的功能是路由(routing)系统,它允许我们在不同的URL之间导航并加载不同的组件。而<router-ou…...
设计模式详解-桥接模式
类型:结构型模式 实现原理:将抽象类和实现类分离,使其独立,然后使用接口再将二者连接起来。 意图:将抽象部分与实现部分分离,使它们都可以独立的变化。 主要解决:类变化频繁时用继承可能会出…...
设计模式—— 单一职责原则
文章目录 设计模式的目的设计模式原则单一职责原则基本介绍应用实例单一职责原则注意事项和细节 设计模式的目的 1,代码重用性(即:相同功能的代码,不用多次编写) 2,可读性(即:编程…...
嵌入式系统中如何选择RTC电池?
RTC(Real Time Clock)是一种用于提供系统时间的独立定时器,它可以在系统断电或低功耗模式下继续运行,只需要一个后备电池作为供电源。在嵌入式系统中,选择合适的RTC电池时非常关键的,它会影响系统时间的准确…...
56 | 国内游戏直播竞品分析
国内游戏直播竞品分析 一、需求分析 当前直播用户群可分为两大类: 主播观众用户需求: 1.主播: 作为直播内容的创造者,主播表现方式和内容很大程度上决定了观众的需求, 其中主播主要只有三点需求: (一) 通过某一手段(如游戏技术、唱歌技巧)获取他人关注,满足虚荣心…...
STM32 CubeMX (第一步Freertos任务管理:创建、删除、挂起、恢复)
STM32 CubeMX Freertos STM32 CubeMX (Freertos任务:创建、删除、挂起、恢复) STM32 CubeMX Freertos前言一、STM32 CubeMX 配置时钟树配置HAL时基选择TIM1(不要选择滴答定时器;滴答定时器留给OS系统做时基)…...
0101读写分离测试-jdbc-shardingsphere-中间件
文章目录 1 前言2、创建SpringBoot程序2.1、创建项目2.2、添加依赖2.3、生成实体类、service与Mapper1.5、配置读写分离 2、测试2.1、读写分离测试2.2、事务测试2.3、负载均衡测试 结语 1 前言 shardingshpere-jdbc定位为轻量级 Java 框架,在 Java 的 JDBC 层提供的…...
sqlite3将词典导入数据库
使用sqlite3代码实现将词典导入数据库中 #include <head.h> #include <sqlite3.h> #include <strings.h> #include <unistd.h> int main(int argc, const char *argv[]) {sqlite3 *db NULL;if(sqlite3_open("./dict.db",&db) ! SQLITE…...
浏览器 - 事件循环机制详解
目录 1,浏览器进程模型进程线程浏览器的进程和线程1,浏览器进程2,网络进程3,渲染进程 2,渲染主线程事件循环异步同步 JS 为什么会阻塞渲染任务优先级 3,常见面试题1,如何理解 js 的异步2&#x…...
析构函数中不应该抛出异常(摘录)
析构函数中抛出异常时概括性总结 从语法上面讲,析构函数抛出异常是可以的,C并没有禁止析构函数引发异常,但是C不推荐这一做法,从析构函数中抛出异常是及其危险的。 如果析构函数抛出异常,则异常点之后的程序不会执行&a…...
Windows定时任务计划无法显示任务程序界面的问题解决
笔者这两天写了一个python脚本程序,用来自动从公司的主数据系统获取数据,并按格式编制成excel。脚本程序编写一切顺利,运行结果很是完美,笔者很是舒心。但在最后一步,用上班的电脑每天早上定时运行它时,出了…...
【Azure API 管理】APIM如何实现对部分固定IP进行访问次数限制呢?如60秒10次请求
问题描述 使用Azure API Management, 想对一些固定的IP地址进行访问次数的限制,如被限制的IP地址一分钟可以访问10次,而不被限制的IP地址则可以无限访问? ChatGPT 解答 最近ChatGPT爆火,所以也把这个问题让ChatGPT来解答&#x…...
Python学习笔记_进阶篇(二)_django知识(一)
本章简介: Django 简介Django 基本配置Django urlDjango viewDjango 模板语言Django Form Django 简介 Django是一个开放源代码的Web应用框架,由Python写成。采用了MVC的软件设计模式,即模型M,视图V和控制器C。它最初是被开发来…...
【hive】hive中row_number() rank() dense_rank()的用法
hive中row_number() rank() dense_rank()的用法 一、函数说明 主要是配合over()窗口函数来使用的,通过over(partition by order by )来反映统计值的记录。 rank() over()是跳跃排序,有两个第二名时接下来就是第四名(同样是在各个分组内)dense_rank() …...
【云原生】【k8s】Kubernetes+EFK构建日志分析安装部署
目录 EFK安装部署 一、环境准备(所有主机) 1、主机初始化配置 2、配置主机名并绑定hosts,不同主机名称不同 3、主机配置初始化 4、部署docker环境 二、部署kubernetes集群 1、组件介绍 2、配置阿里云yum源 3、安装kubelet kubeadm …...
计算实数数组中所有元素的绝对值 numpy.fabs()
【小白从小学Python、C、Java】 【计算机等级考试500强双证书】 【Python-数据分析】 计算实数数组中所有元素的绝对值 numpy.fabs() [太阳]选择题 请问关于以下代码表述错误的是? iimport numpy as np a np.array([-1,-3]) b np.array([-1,34j]) print("【显…...
深入浅出Pytorch函数——torch.nn.init.orthogonal_
分类目录:《深入浅出Pytorch函数》总目录 相关文章: 深入浅出Pytorch函数——torch.nn.init.calculate_gain 深入浅出Pytorch函数——torch.nn.init.uniform_ 深入浅出Pytorch函数——torch.nn.init.normal_ 深入浅出Pytorch函数——torch.nn.init.c…...
ORACLE中UNION、UNION ALL、MINUS、INTERSECT学习
1、UNION和UNION ALL的使用与区别 如果我们需要将两个select语句的结果作为一个整体显示出来,我们就需要用到union或者union all关键字。union的作用是将多个结果合并在一起显示出来。 union和union all的区别是union会自动压缩多个结果集合中的重复结果ÿ…...
【k8s、云原生】基于metrics-server弹性伸缩
第四阶段 时 间:2023年8月18日 参加人:全班人员 内 容: 基于metrics-server弹性伸缩 目录 一、Kubernetes部署方式 (一)minikube (二)二进制包 (三)Kubeadm 二…...
回归预测 | MATLAB实现WOA-SVM鲸鱼算法优化支持向量机多输入单输出回归预测(多指标,多图)
回归预测 | MATLAB实现WOA-SVM鲸鱼算法优化支持向量机多输入单输出回归预测(多指标,多图) 目录 回归预测 | MATLAB实现WOA-SVM鲸鱼算法优化支持向量机多输入单输出回归预测(多指标,多图)效果一览基本介绍程…...
VSCode快捷键
CtrlShiftP,F1:显示命令面板 CtrlP:快速打开 CtrlShiftN:新窗口/实例 CtrlShiftW:关闭窗口/实例 CtrlX:剪切行 CtrlC:复制行 ALT↑/↓:上下移动 ShiftAlt↓/↑:向…...
贪心算法求数组中能组成三角形的最大周长
题目:三角形的最大周长 给定由一些正数(代表长度)组成的数组arr,返回由其中三个长度组成的、面积不为零的三角形的最大周长。 如果不能形成任何面积不为零的三角形,返回0。 分析: 对数组排序,再从大到小选择三个数,再…...
VMWare Workstation 17 Pro 网络设置 桥接模式 网络地址转换(NAT)模式 仅主机模式
文章目录 网络模式配网要求CentOSDHCP虚拟网络桥接模式默认配置测试手动配置测试 网络地址转发模式 (NAT)还原配置虚拟网络配置默认配置测试手动配置测试 仅主机模式 网络模式 桥接模式: 主机与虚拟机对等, 虚拟机注册到主机所在的局域网, 会占用该网络的IP该局域网内的所有机…...
拒绝摆烂!C语言练习打卡第四天
🔥博客主页:小王又困了 📚系列专栏:每日一练 🌟人之为学,不日近则日退 ❤️感谢大家点赞👍收藏⭐评论✍️ 目录 一、选择题 📝1.第一题 📝2.第二题 Ὅ…...
KubeSphere 社区双周报 | Java functions framework 支持 SkyWalking | 2023.8.4-8.17
KubeSphere 社区双周报主要整理展示新增的贡献者名单和证书、新增的讲师证书以及两周内提交过 commit 的贡献者,并对近期重要的 PR 进行解析,同时还包含了线上/线下活动和布道推广等一系列社区动态。 本次双周报涵盖时间为:2023.08.04-2023.…...
【学习笔记之java】使用RestTemplate调用第三方接口
1.首先需要导入依赖 <!-- RestTemplate使用导入的依赖--><dependency><groupId>org.apache.httpcomponents</groupId><artifactId>httpclient</artifactId><version>4.5.13</version></dependency>2.跟启动类同级创建…...
数据集成革新:去中心化微服务集群的无限潜能
在当今数据密集型的业务环境下,传统的集中式架构已经难以满足高可用性和高并发性的要求。而去中心化微服务集群则通过分散式的架构,将系统划分为多个小型的、独立部署的微服务单元,每个微服务负责特定的业务功能,实现了系统的高度…...
后端返回可下载的xlsx文件,但是前端接收下载后为乱码
我的接收数据进行处理的代码为: download_signal_list() {return new Promise((resolve, reject) > {get_download_signal({project_id: this.projectId,version_id: this.versionId}).then(response > {const url window.URL.createObjectURL(new Blob([res…...
提升资源管理效率必备工具推荐
一、数据传输 1、Textify(PC) 作为一名技术人员,需要经常研究各种技术,因此,复制粘贴的操作十分常见。 Textify可以快速复制各种控件中的文本,包括浏览器中当前页面的标题、聊天窗口中各个部分的文字、桌…...
HJ23 删除字符串中出现次数最少的字符
描述 实现删除字符串中出现次数最少的字符,若出现次数最少的字符有多个,则把出现次数最少的字符都删除。输出删除这些单词后的字符串,字符串中其它字符保持原来的顺序。 数据范围:输入的字符串长度满足 1≤n≤20 1≤n≤20 &…...
文心一言 VS 讯飞星火 VS chatgpt (76)-- 算法导论7.3 1题
一、如果用go语言,为什么我们分析随机化算法的期望运行时间,而不是其最坏运行时间呢? 文心一言: 在分析算法的性能时,期望运行时间是一个重要的指标,它描述了算法在平均情况下的表现。期望运行时间考虑了所有可能的…...
Leetcode - 滑动窗口
文章目录 1. 滑动窗口2. 举例2.1 无重复字符的最长子串2.2 长度最小的子数组2.3 滑动窗口最大值2.4 最小覆盖子串2.5 删除有序数组中的重复项 1. 滑动窗口 滑动窗口的大概思想如下: 可以通过两个指针来标识窗口的边界。窗口的长度是可以固定的,也可以是…...
如何保证数据传输的安全?
要确保数据传输的安全,您可以采取以下措施: 使用加密协议:使用安全的传输协议,如HTTPS(HTTP over SSL/TLS)或其他安全协议,以保护数据在传输过程中的安全性。加密协议可以有效防止数据被窃听或篡改。 强化身份验证&…...
政务、商务数据资源有效共享:让数据上“链”,记录每一个存储过程!
数据上链是目前“区块链”最常见的场景。因为链上所有参与方都分享了统一的事实来源,所有人都可以即时获得最新的信息,数据可用不可见。因此,不同参与方之间的协作效率得以大幅提高。同时,因为区块链上的数据难以篡改,…...
xml转map工具类
背景:最近遇到接口返回是xml,所以需要整一个转换的工具类,方便后续其他xml处理。 依赖引入: <dependency><groupId>dom4j</groupId><artifactId>dom4j</artifactId><version>1.1</versi…...
C++并发多线程--std::future_status、std::shared_future和std::atomic的使用
1--std::future_status的使用 std::future_status成员函数含有三种状态:timeout(执行超时)、ready(执行完毕)和deferred(延迟执行),其中 deferred 状态需要用 std::launch::deferred…...
Redis在Java中的基本使用
本片将介绍 Redis 在 Java 中的基本使用 文章目录 1、使用jedis操作redis1.1、Jedis简介1.2、引入jedis的Maven依赖1.2、获取连接1.3、使用实例 2、对于JedisPooled的使用2.1、使用JedisPooled2.2、关于连接池 3、SpringBoot下使用Redis3.1、引入Maven依赖3.2、配置Redis连接3.…...
4.2 C++ Boost 内存池管理库
Boost 库是一个由C/C语言的开发者创建并更新维护的开源类库,其提供了许多功能强大的程序库和工具,用于开发高质量、可移植、高效的C应用程序。Boost库可以作为标准C库的后备,通常被称为准标准库,是C标准化进程的重要开发引擎之一。…...
Django模型基础
文章目录 一、models字段类型概述属性命名限制使用方式逻辑删除和物理删除常用字段类型 二、常用字段参数常用字段选项(通过字段选项,可以实现对字段的约束) 实践创建模型执行迁移命令 并 创建超级用户登录admin后台添加文件和图片字段定义模型字段和约束及在Admin后…...
导读-Linux简介
Linux简介 总所周知,计算机系统包含硬件和软件两部分。硬件部分被称为裸机,主要包括中央处理器(CPU)、内存、外存和各种外部设备。软件部分主要包括系统软件和应用软件两部分。系统软件包括操作系统、汇编语言、编译程序、数据…...
判断平面中两射线是否相交的高效方法
1. 简介 最近在工作中遇到判断平面内两射线是否相交的问题。 对于这个问题的解决,常规的方法是将两条射线拓展为直线,计算直线的交点,而后判断交点是否在射线上。 这种方法,在思路上较为直观,也易于理解。然后,该方法在计算量上相对较大。对于少量射线间的交点计算尚可…...
基于VUE3+Layui从头搭建通用后台管理系统(前端篇)八:自定义组件封装上
一、本章内容 本章实现一些自定义组件的封装,包括数据字典组件的封装、下拉列表组件封装、复选框单选框组件封装、单选框组件封装、文件上传组件封装、级联选择组件封装、富文本组件封装等。 1. 详细课程地址: 待发布 2. 源码下载地址: 待发布 二、界面预览 ![在这里插入图…...
RabbitMq交换机类型介绍
RabbitMq交换机类型介绍 在RabbitMq中,生产者的消息都是通过交换器来接收,然后再从交换器分发到不同的队列,再由消费者从队列获取消息。这种模式也被成为“发布/订阅”。 分发的过程中交换器类型会影响分发的逻辑。 直连交换机:…...
中国电信秋招攻略,考试内容分析
电信秋招简介 每年的毕业生人数都在逐年递增,逐年递增就意味着竞争会越来越大,最好比别人做更充足的准备。要确定好就业方向以及就业的岗位,要了解各种各样的流程,做好一切自己能做到的准备。而对于有想法进入电信公司工作的人来…...
prompt-engineering-note(面向开发者的ChatGPT提问工程学习笔记)
介绍: ChatGPT Prompt Engineering Learning Notesfor Developers (面向开发者的ChatGPT提问工程学习笔记) 课程简单介绍了语言模型的工作原理,提供了最佳的提示工程实践,并展示了如何将语言模型 API 应用于各种任务的应用程序中。 此外&am…...
2011-2021年数字普惠金融指数Bartik工具变量法(含原始数据和Bartik工具变量法代码)
2011-2021年数字普惠金融指数Bartik工具变量法(含原始数据和Bartik工具变量法代码) 1、时间:2011-2020(省级、城市),2014-2020(区县) 2、原始数据来源:北大金融研究中心…...