现在有 105 个用户，编号为 1- 105，现在已知有 m 对关系，每一对关系给你两个数 x 和 y ，代表编号为 x 的用户和编号为 y 的用户是在一个圈子中，例如： A 和 B 在一个圈子中， B 和 C 在一个圈子中，那么 A , B , C 就在一个圈子中。现在想知道最多的一个圈子内有多少个用户。
数据范围： 
进阶：空间复杂度%20%5C)
，时间复杂度 %20%5C)
进阶：空间复杂度
[编程题]朋友圈(后端开发卷)
- 热度指数：8058 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行输入一个整数T，接下来有T组测试数据。
对于每一组测试数据：第一行输入1个整数n，代表有n对关系。接下来n行，每一行输入两个数x和y，代表编号为x和编号为y的用户在同一个圈子里。1 ≤ T ≤ 101 ≤ n ≤ 2*1061 ≤ 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
并查集解法 借鉴了 @onestan 的并查集解法，封装成类，方便阅读 不懂并查集可以看 B 站宝藏 UP 主 @正月点灯笼 的视频讲解：并查集 #include <bits/stdc++.h>
using namespace std;
class friendsCircle
{
展开全文
使用全局变量得方法。 记得递归find方法。 人头从1重新开始编号，所以需要map。 #include<bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 5;
int par[MAX_N], cnt[MAX_N]
展开全文
并查集，对这一知识点不太清楚的小伙伴可以看看这篇文章：并查集。 细节见代码注释 #include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin>>T;
int n,x,y,m
展开全文
题目的做法就是考察并查集，由于数据量较大，直接查询父节点会超时，需要在find中加上路径压缩，就是将将id数组从父节点改为祖父节点，这样更快在union过程中，将小树向大树合并与将矮树向高树合并差不多，我用的是后者 import java.util.Scanner;
//题目的做法是实现一个并查集
展开全文
并查集
涉及集合之间的关系，核心是每个元素最终都将唯一指向某个自旋元素，统计这样的元素数目以及它们出现的次数，即可得到每个集合的大小。需要注意的是初始时每个元素并非自旋，可以在查找其父节点而不可得的时候将其设置为自旋，当使用秩时，只有自旋节点的秩是有价值的，也可以在第一次查找到自旋节点时设置。
#i
展开全文
问题信息
通过挑战的用户
-
2023-02-28 17:40:51 -
2023-02-11 19:31:10
-
2023-01-16 19:21:19 -
2022-11-28 13:50:47 -
2022-11-07 20:15:53
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
