军训分批(codevs 2751)
2024-08-30 09:32:33
题目描述 Description
某学校即将开展军训。共有N个班级。
前M个优秀班级为了保持学习优势,必须和3位任课老师带的班级同一批。
问共有几批?
输入描述 Input Description
N,M
老师教的其他班级(M行)
输出描述 Output Description
批次数
样例输入 Sample Input
4 2
1 1 1
2 3 1
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
对于50%数据,N,M<=1000.
对于100%数据,N,M<=30000,N<=M.
/*
迷之题意
先说下题目意思吧:
给定n个班级,m个优秀班级,对于每个优秀班级,给出3名老师,数值代表每个老师还教着哪个班。教同一个班的三名老师必须同一批次,问需要多少批次。 因为教同一个班的三名老师必须同一批次,所以对于每一个优秀班级,都最多有可能有另外3个班和它同一批次,我们就用并查集将它们合并,以求出答案。
*/
#include<cstdio>
#include<iostream>
#define M 30010
using namespace std;
int fa[M];
int find(int x)
{
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)fa[i]=i;
for(int i=;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
int r=find(i),a=find(x),b=find(y),c=find(z);
if(r!=a)fa[a]=r;
if(r!=b)fa[b]=r;
if(r!=c)fa[c]=r;
}
int ans=;
for(int i=;i<=n;i++)
if(fa[i]==i)ans++;
printf("%d",ans);
return ;
}
最新文章
- [AlwaysOn Availability Groups]排查:AG超过RPO
- Quartz 线程处理
- uva 1368 DNA Consensus String
- c/c++常用代码--udp多播
- Android新建项目 默认布局改为 LinearLayout
- 使用SndPlaySound从内存中播放WAV
- Widows 和Linux 查看和操作端口方法
- c语言五子棋
- Laravel 5.6: Specified key was too long error
- Selenium之WebDriver元素定位方法
- Hadoop的RPC机制及简单实现
- hdu2289二分答案 圆台体积
- 化学1(chem1)- 化学合成
- Vim global命令和重复操作
- APN与VPDN的主要区别
- Java游戏服务器成长之路——感悟篇
- ubuntu如何释放内存
- centOS安装openoffice的方法
- Why won&#39;t JRockit find my classes
- OSG 中文解决方案 【转】