首页 > 试题广场 >

集合合并

[编程题]集合合并

给定若干个32位int数字集合，每个集合中的数字无重复，譬如：
{1,2,3} {2,5,6} {8}
将其中交集不为空的集合合并，保证合并完成后所有集合之间无交集，输出合并后的集合个数以及最大集合中元素的个数。

输入格式：
1. 第一行为一个数字N，表示集合数。
2. 接下来N行，每行一个非空集合，包含若干个数字，数字之间用空格分开。
假设第i个集合的大小为Si，数据满足N<=100000,ΣSi<=500000

输出格式：
1. 第一行为合并后的集合个数。
2. 第二个为最大集合中元素的个数。

示例1

输入

2
5

算法知识视频讲解

bandiaoz

发表于 2024-12-28 21:52:05

解题思路这是一道并查集问题，主要思路如下：数据结构：使用并查集维护集合关系使用 map 对数字进行离散化处理使用 vector 存储每个集合的元素处理步骤：读入每个集合的元素并进行离散化对每个集合内的元素进行合并统计最终的集合数量和最大集合大小关键点：使用展开全文

C++工程师数组小米集团模拟测试工程师图 2019 Java工程师

来自：小米2019秋招软件开...

上传者：小小

难度：

11条回答 59收藏 7795浏览

查看代码

集合合并

扫一扫，把题目装进口袋