（模板）并查集
题目描述：
体育课上，体育老师牛牛弄不清学生们都是哪个班级的，他只能随便找两个同学，问他们是不是一个班的，牛牛记下了属于同一个班的学生的序号，但是他弄不清自己教的班级的情况，请你帮助他。
假设体育老师的学生有n人，学号分别是1,2,...n，他的小本本记录了m行，每行记下了属于一个班
展开全文
考虑到题目需要求出人数最多的班级，也就是秩最大的班级，引入ranks数组记录，同时小挂大似乎也是一种优化，最后的班级数量再来一遍遍历，如果父节点是自身，说明它就是该集合的父节点(已经使用了路径压缩)
#include<bits/stdc++.h>
using namespace std;
展开全文
#include<iostream>
using namespace std;
const int N = 1e5+10;
int f[N],g[N];
int find(int x)
{
if(f[x]!=x) return f[x]=find(f[x]);
els
展开全文
使用并查集，来记录所有人的关系
再将每个人的顶送入set中，set的长度就是班级数量
再用一个循环找到最大班级即可
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int st[N], f[N],
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
