C++代码实现 小计是一个程序员,他为学校做了一个校园聊天系统,已知系统中有 n 名用户,编号为 1~n,现在已知有 m 对好友关系,每一对关系由两个整数 x 和 y 组成 ,表示编号为 x 的用户和编号为 y 的用户是一对好友,请问校园中有多少个圈子,人数最多的圈子有多少人。 圈子:一个圈子中的人一定直接与同圈子的其他人是好友,或者通过若干名同圈子的人,间接与同圈子的其他人是好友。 小计是一个程序员,他为学校做了一个校园聊天系统,已知系统中有 n 名用户,编号为 1~n,现在已知有 m 对好友关系,每一对关系由两个整数 x 和 y 组成 ,表示编号为 x 的用户和编号为 y 的用户是一对好友,请问校园中有多少个圈子,人数最多的圈子有多少人。 圈子:一个圈子中的人一定直接与同圈子的其他人是好友,或者通过若干名同圈子的人,间接与同圈子的其他人是好友。

时间: 2023-11-27 13:55:37 浏览: 114
以下是C++代码实现: ```cpp #include <iostream> #include <vector> using namespace std; const int MAXN = 1005; int n, m; int fa[MAXN], size[MAXN]; void init() { for (int i = 1; i <= n; i++) { fa[i] = i; size[i] = 1; } } int find(int x) { if (fa[x] == x) return x; return fa[x] = find(fa[x]); } void unite(int x, int y) { int fx = find(x), fy = find(y); if (fx == fy) return; if (size[fx] < size[fy]) swap(fx, fy); fa[fy] = fx; size[fx] += size[fy]; } int main() { cin >> n >> m; init(); for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; unite(x, y); } int cnt = 0, max_size = 0; for (int i = 1; i <= n; i++) { if (fa[i] == i) cnt++; max_size = max(max_size, size[i]); } cout << cnt << endl; cout << max_size << endl; return 0; } ``` 思路解析: 题目要求我们求出圈子的个数和人数最多的圈子的人数,这是一道典型的并查集问题。 首先使用 `init()` 函数初始化每个节点的父节点为自己,大小为1。接下来遍历所有的好友关系,使用 `unite()` 函数将两个好友所在的集合合并。最后遍历所有的节点,统计圈子的个数和人数最多的圈子的人数。 其中,`find()` 函数用于查找一个节点所在的集合,使用路径压缩优化可以提高效率。`unite()` 函数用于合并两个集合,按秩合并可以保证并查集的效率。 时间复杂度分析:使用路径压缩和按秩合并优化后,每次操作的时间复杂度为 O(logn),总共有 m 次操作,所以总时间复杂度为 O(mlogn)。空间复杂度为 O(n)。
阅读全文

相关推荐

最新推荐

recommend-type

C++实现病人就医管理系统

"C++实现病人就医管理系统" 在本文中,我们将详细介绍如何使用C++语言实现病人就医管理系统。该系统主要包括病人排队、医生排班、病人就医记录等功能模块。 首先,我们需要定义一个链队列类模板LinkQueue,以便...
recommend-type

C++实现机票预订系统

"C++实现机票预订系统" 本文将详细介绍C++实现机票预订系统的设计和实现。该系统主要包括航班管理和机票预订两个部分。我们将使用C++语言来实现该系统,并对系统的设计和实现进行详细的分析和解释。 一、系统设计 ...
recommend-type

C++ 学生成绩管理系统设计报告书

学生成绩管理系统是一种基于C++的面向对象程序设计的应用,旨在提供一套全面的功能,用于管理学生的基本信息、考试成绩以及进行数据分析。以下是该系统的主要设计和实现细节: **一、系统需求分析** 系统的主要...
recommend-type

C++学校人员信息管理系统课程设计.doc

该课程设计是一个使用C++语言开发的学校人员信息管理系统,旨在为大一大二学生提供一个实践性强的课程设计项目。该系统的开发使用到了C++语言的基本语法操作,如链表、文件读写等。 知识点1:链表的应用 在该系统中...
recommend-type

C++实现两个有序数组的合并

以下是一个使用C++语言实现数组合并的示例程序: ```cpp int main() { int n1,n2; cin&gt;&gt;n1&gt;&gt;n2; int a[n1],b[n2]; for(int i = 0; i; ++i){ cin&gt;&gt;a[i]; } for(int i=0;i;++i){ cin&gt;&gt;b[i]; } insert(a, b, ...
recommend-type

菲格瑞思压力传感器原理探究

资源摘要信息:"菲格瑞思压力传感器工作原理简介" 菲格瑞思(Futek)是一家知名的传感器制造商,其产品广泛应用于工业、科研和消费类市场。本文档的目的是对菲格瑞思公司的压力传感器的工作原理进行简单了解。在正式讨论之前,首先需要明确一些基本概念,如压力传感器的定义、类型以及它们的工作原理。 压力传感器是一种检测装置,能够感受到被测量的压力,并将其转换为可用的输出信号。输出信号可以是模拟电压、电流信号,也可以是数字信号,这取决于传感器的内部电路和设计。根据不同的测量原理,压力传感器大致可分为电阻式、电容式、压电式、电磁式等多种类型。 电阻式压力传感器是最常见的一种类型,它通常是基于应变片技术。应变片是一种电阻材料,当它受到拉伸或压缩时,其电阻值会发生变化。在压力传感器中,应变片被粘贴到一个弹性体上,弹性体在受到压力作用时会产生变形。这种变形会导致应变片的电阻值发生变化,通过测量这种变化,就可以计算出施加的压力。 菲格瑞思压力传感器很可能使用了类似的原理。它可能包含了一个或多个应变片,当传感器感受到外部压力时,弹性体产生微小变形,导致应变片的电阻值产生变化。这一电阻变化会被传感器内的电路检测并转换成电信号,从而实现压力到电信号的转换。 电容式压力传感器则利用电容变化来检测压力变化。这种传感器通常由两个电极板和一个可移动的隔板组成。当压力作用于隔板上时,隔板会移动,改变电极板之间的距离,从而改变了两电极之间的电容量。测量电容的变化即可得知压力的大小。 压电式压力传感器基于压电效应,当某些材料(如石英晶体)受到压力时会在其两端产生电荷。这种电荷的产生与材料受到的压力成正比,因此可以作为测量压力的一种手段。 电磁式压力传感器则是利用变化的压力引起电磁场的改变来进行测量。这种传感器一般用于液位测量或非接触式压力测量。 了解了这些基本概念后,我们可以通过阅读文档“对菲格瑞思压力传感器的工作原理进行简单的了解.doc”来获取菲格瑞思公司产品特有的信息。文档中可能会详细描述该公司的压力传感器如何工作,包括其设计细节、如何实现精确测量,以及在不同应用场景下如何保持性能等。 在阅读文档时,应关注以下方面: 1. 传感器的构造和工作原理,包括它是如何将压力转换为电信号的。 2. 传感器的精确度、稳定性和可靠性,这对于工业应用尤其重要。 3. 传感器在不同环境下的性能,包括温度、湿度和压力范围的影响。 4. 传感器的输出特性,如它的线性度、滞后性和重复性。 5. 传感器的应用领域,这有助于了解在特定行业中如何选择和使用传感器。 通过上述内容,我们可以得出菲格瑞思压力传感器是一个用于检测压力变化并将其转换为电信号的精密设备。了解其工作原理有助于正确选择和应用这些传感器,以满足不同场合的精确测量需求。同时,细致研究该公司的产品文档也是获取详细技术信息和参数的重要途径。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

GitHub高效管理秘籍:开源项目管理的10大实用技巧

![GitHub高效管理秘籍:开源项目管理的10大实用技巧](https://opengraph.githubassets.com/ae4901c7b2a37ac96ae797d902ca8816bcf70e1da498ce48ec16ad4d02f308fc/cwgem/Ruby-Documentation-Translation-Project) # 1. 开源项目管理的概述与GitHub基础 在当今的软件开发领域中,开源项目管理已经成为不可或缺的一部分。借助于GitHub等代码托管平台,开发者可以协作编写、共享代码,并管理项目的所有相关活动。本章将带你进入开源项目管理的世界,重点介绍其
recommend-type

回天TM系列如何利用CDP技术实现持续数据保护,并在企业级环境中提高数据备份与恢复的效率和精确性?

回天TM系列产品采用CDP(Continuous Data Protection)技术,为企业提供了实时数据备份和快速数据恢复的解决方案。CDP技术的核心优势在于其能够持续监控数据变化,并立即捕获所有数据的更新,从而实现几乎零数据丢失的备份。 参考资源链接:[蓝海本立回天TM系列:实时数据备份与恢复技术详解](https://wenku.csdn.net/doc/88sina3vqm?spm=1055.2569.3001.10343) 在企业级环境中,CDP技术通过以下几个方面提高了数据备份与恢复的效率和精确性: 1. 实时监控:CDP技术通过持续监控数据变化,确保了数据的实时备份。它不
recommend-type

求职者的福音:免费分享高颜值简历模板

资源摘要信息:"本资源是一个关于求职简历模板的分享,适用于大学生、应届生以及寻求实习机会的在校生。提供了多种简历模版,包括简约大气的风格、高颜值的设计等,满足不同求职者的需求。内容涵盖了个人信息、求职意向、教育背景、工作经验、技能和能力、实习与项目经验、获奖和荣誉、自我评价以及兴趣爱好等方面,旨在帮助求职者全面而专业地展示自我,提高求职成功率。" 标题中的知识点: - 简历模版:说明了资源是关于提供多种简历模板,供求职者下载使用。 - 应届生:指出了该简历模板适合的特定群体,即即将毕业或刚刚毕业的大学生。 - 高颜值简历模版:强调了简历设计的美观性,通常高颜值的设计能给人留下良好的第一印象。 - 个人简历模版:指明了这是一套针对个人求职需求的简历模板。 - 简约大气:描述了简历设计的风格特点,简约而大气的设计往往给人以专业感。 - 大学生在校生:指出了除应届生外,大学生在校生也是该简历模板的适用人群。 - 求职:说明了使用简历的目的,即求职。 - 实习:指出了除了全职工作外,该简历模板也可用于寻找实习机会。 描述中的知识点: - 简历格式:详细介绍了简历的基本结构和应该包含的主要内容。 - 头部信息:列出了简历开头需要提供的个人基本信息,如姓名、联系方式等。 - 求职目标:说明了在简历中可选择性地阐述个人的职业意向和目标,以吸引招聘方的注意。 - 教育背景:描述了如何清晰地列出个人的教育经历,包括学校、专业和就读时间等。 - 工作经验:指导如何有条理地呈现以往的工作经历,包括公司、职位、时间以及工作职责和成就。 - 技能和能力:强调了在简历中展示与职位相关的专业技能、语言能力和计算机技能的重要性。 - 实习经验/项目经验:指出如果有实习或项目经验,应当在简历中予以体现,以增强简历的竞争力。 - 获奖和荣誉:说明了添加在学术、工作或其他领域获得的奖项和荣誉,可以增加求职者的竞争力。 - 自我评价:讨论了求职者可提供对自身特点、能力和职业目标的简短描述,帮助招聘方了解个人性格和职业规划。 - 兴趣爱好:建议了在简历中适当列出兴趣爱好,可以展示求职者的多样性和个人素质。 - 参考人:提醒了如有推荐人,可以在简历中提供参考人的联系信息,以便招聘方进行背景调查。 标签中的知识点: - 范文/模板/素材:强调了资源提供的简历为模板形式,用户可以直接下载使用或作为参考进行修改。 - 简历:明确了该资源的主题,即与求职简历相关的内容。 压缩包子文件的文件名称列表中的知识点: - 54.docx:表示资源的压缩包中包含了以docx格式命名的Word文档,即具体的一个简历模板文件。 综上所述,资源提供的是一套适合大学生和应届生使用的求职简历模板,设计风格简约而具有吸引力,内容全面且实用,旨在帮助求职者更好地展示自己的专业技能和个人素质,从而提高求职成功率。资源的下载和使用能够方便快捷地帮助求职者制作出专业的简历。