首页 > 试题广场 >

朋友圈(后端开发卷)

[编程题]朋友圈(后端开发卷)
  • 热度指数：8068 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
现在有 105 个用户，编号为 1- 105，现在已知有 m 对关系，每一对关系给你两个数 x 和 y ，代表编号为 x 的用户和编号为 y 的用户是在一个圈子中，例如： A 和 B 在一个圈子中， B 和 C 在一个圈子中，那么 A , B , C 就在一个圈子中。现在想知道最多的一个圈子内有多少个用户。

数据范围：
进阶：空间复杂度 ，时间复杂度

输入描述:
第一行输入一个整数T，接下来有T组测试数据。
对于每一组测试数据：第一行输入1个整数n，代表有n对关系。
接下来n行，每一行输入两个数x和y，代表编号为x和编号为y的用户在同一个圈子里。
1 ≤ T ≤ 10
1 ≤ n ≤ 2*106
1 ≤ x, y ≤ 105


输出描述:
对于每组数据，输出一个答案代表一个圈子内的最多人数
示例1

输入

2
4
1 2
3 4
5 6
1 6
4
1 2
3 4
5 6
7 8

输出

4
2
算法知识视频讲解
开通博客
头像 鹿邑斯塔克
发表于 2021-09-02 21:45:35
并查集解法 借鉴了 @onestan 的并查集解法，封装成类，方便阅读 不懂并查集可以看 B 站宝藏 UP 主 @正月点灯笼 的视频讲解：并查集 #include <bits/stdc++.h> using namespace std; class friendsCircle { 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 大厂算法岗必拿下
发表于 2021-09-02 22:26:41
使用全局变量得方法。 记得递归find方法。 人头从1重新开始编号，所以需要map。 #include<bits/stdc++.h> using namespace std; const int MAX_N = 2e5 + 5; int par[MAX_N], cnt[MAX_N] 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 onestan
发表于 2021-08-12 16:30:09
并查集，对这一知识点不太清楚的小伙伴可以看看这篇文章：并查集。 细节见代码注释 #include<bits/stdc++.h> using namespace std; int main() { int T; cin>>T; int n,x,y,m 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 孤星丶泪
发表于 2021-09-03 15:14:22
题目的做法就是考察并查集，由于数据量较大，直接查询父节点会超时，需要在find中加上路径压缩，就是将将id数组从父节点改为祖父节点，这样更快在union过程中，将小树向大树合并与将矮树向高树合并差不多，我用的是后者 import java.util.Scanner; //题目的做法是实现一个并查集 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 wolverine12138
发表于 2022-01-08 09:07:26
并查集 涉及集合之间的关系，核心是每个元素最终都将唯一指向某个自旋元素，统计这样的元素数目以及它们出现的次数，即可得到每个集合的大小。需要注意的是初始时每个元素并非自旋，可以在查找其父节点而不可得的时候将其设置为自旋，当使用秩时，只有自旋节点的秩是有价值的，也可以在第一次查找到自旋节点时设置。 #i 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 腾讯 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
47条回答 13444浏览

热门推荐

通过挑战的用户

相关试题

朋友圈(后端开发卷)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号