题目描述 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 ;
}

最新文章

  1. [AlwaysOn Availability Groups]排查:AG超过RPO
  2. Quartz 线程处理
  3. uva 1368 DNA Consensus String
  4. c/c++常用代码--udp多播
  5. Android新建项目 默认布局改为 LinearLayout
  6. 使用SndPlaySound从内存中播放WAV
  7. Widows 和Linux 查看和操作端口方法
  8. c语言五子棋
  9. Laravel 5.6: Specified key was too long error
  10. Selenium之WebDriver元素定位方法
  11. Hadoop的RPC机制及简单实现
  12. hdu2289二分答案 圆台体积
  13. 化学1(chem1)- 化学合成
  14. Vim global命令和重复操作
  15. APN与VPDN的主要区别
  16. Java游戏服务器成长之路——感悟篇
  17. ubuntu如何释放内存
  18. centOS安装openoffice的方法
  19. Why won&#39;t JRockit find my classes
  20. OSG 中文解决方案 【转】

热门文章

  1. 推荐一个markdown格式转html格式的开源JavaScript库
  2. C语言二维数组作为函数参数
  3. 几句话总结一个算法之RNN、LSTM和GRU
  4. springboot-i18n国际化
  5. Hibernate 多表查询 - Criteria添加子字段查询条件 - 出错问题解决
  6. github+hexo+themes搭建简易个性主题博客
  7. Promise中的next 另一个用法
  8. LuoguP1351 联合权值 (枚举)
  9. python3.x中的33个保留字
  10. Elementary OS上eclipse卡死问题