CD收藏 并查集 模版

问题：

lmh平常爱听歌，所以买了很多的CD来收藏，但是因为平常整理不当，所以忘记了这些CD的歌手是谁。现在他想知道他到底收藏了多少位歌手的专辑，于是他想了一个办法，同时拿出两个CD来听，可以分辨出来是否为同一个歌手唱的。（如果没有说明则认为是没有分辨出来，为不同歌手）现在他列了一个表记录哪些专辑是同一歌手，但他面对着这一堆记录不知如何处理，请你告诉他到底他有多少个歌手的专辑。

输入：

第一行n,m。n表示CD的个数（标号分别为1到n），m表示lmh所分辨出来的共有几组。接下来的m行每一行有两个数a,b。表示a唱片和b唱片是同一个歌手。（1<=n，m<=10000）

输出：

总计的歌手数量。

朴素代码简单易懂，欢迎新手看过问题解析后来理解代码

///CD收藏    并查集模版#include
#include
using namespace std;
int a[10000+5];
int geta(int x)                               ///geta函数作用是找到该CD的源头歌手
{if(a[x]==x){return a[x];}else{a[x]=geta(a[x]);        ///不断往前追溯源头歌手return a[x];}
}
bool ss(int x,int y)                            ///ss函数功能为将两个CD合并到一起
{int j,k;j=geta(x);      ///j,k为CD的源头歌手编号k=geta(y);if(j!=k){a[k]=j; ///用a[k]而不用a[y]是为了直接改变本源歌手（将两个歌手合成一个歌手，而不是将一个CD归入到另一个歌手名下）}
}
int main()
{int n,m,x,y,sum;while(scanf("%d %d",&n,&m)!=EOF)               ///n为CD数量     m为CD之间的关系组数{memset(a,0,sizeof(a));for(int i=0; ifor(int i=0; i"%d %d",&x,&y);ss(x,y);                   ///将两个CD合并（右边的并到左边）}sum=0;for(int i=0; iif(a[i]==i){sum++;}}printf("%d\n",sum);                    ///最终输出歌手数量}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！