SDNU 1217 CD收藏——并查集
2024-09-06 06:00:51
Description
lmh平常爱听歌,所以买了很多的CD来收藏,但是因为平常整理不当,所以忘记了这些CD的歌手是谁。现在他想知道他到底收藏了多少位歌手的专辑,于是他想了一个办法,同时拿出两个CD来听,可以分辨出来是否为同一个歌手唱的。(如果没有说明则认为是没有分辨出来,为不同歌手)现在他列了一个表记录哪些专辑是同一歌手,但他面对着这一堆记录不知如何处理,请你告诉他到底他有多少个歌手的专辑。
Input
第一行n,m。n表示CD的个数(标号分别为1到n),m表示lmh所分辨出来的共有几组。接下来的m行每一行有两个数a,b。表示a唱片和b唱片是同一个歌手。(1<=n,m<=10000)
Output
总计的歌手数量。
Sample Input
10 9
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4
Sample Output
3
#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
int find(int x)
{
return x==f[x]?x:f[x]=find(f[x]);
}
void merge(int x,int y)
{
x=find(x),y=find(y);
if(x!=y) f[x]=y;
}
int main()
{
//freopen("in.txt","r",stdin);
int n,m,x,y,ans;
cin>>n>>m;
for(int i=;i<=n;i++) f[i]=i;
for(int i=;i<=m;i++)
{
cin>>x>>y;
merge(x,y);
}
for(int i=;i<=n;i++)
if(f[i]==i) ans++;
cout<<ans<<endl;
}
最新文章
- a标签绝对定位,点击区域被图片遮挡(IE下)
- cocoapods安装及使用
- /etc/profile和$HOME/.bash_profile
- 6步图文教你优化myeclipse2014
- 【Cocos2d入门教程二】Cocos2d-x基础篇
- SVN遇到的几个错误问题解决办法
- [Angular 2] Using Array ...spread to enforce Pipe immutability
- 移动端-H5预加载页面
- Python Requests: Invalid Header Name 解决方法
- MIT许可证
- 转:LINUX/UNIX下的回车换行与WINDOWS下的区别
- Fastcgi、CGI 是什么
- js 实现操作浏览器或者元素的全屏与退出全屏功能
- Codeforces Round #530 (Div. 2) F (树形dp+线段树)
- Dropping tests [POJ2976] [01分数规划]
- vue的cli中自定义router
- 关于jquery所有动画都有速度和动画的方向(在宽度方向上的动画)?
- python及pandas,numpy等知识点技巧点学习笔记
- 人生苦短,我用python
- EF6.0 code first感触