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 <cstdio>
# include <iostream>
using namespace std;
int f[
10010];
int m,n;
void init()
{
for (
int i=
1; i<=n; ++
i)
f[i] =
i;
}
int get (
int v)
{
if (f[v] ==
v)
return v;
else
{
f[v] =
get(f[v]);
//路径压缩
return f[v];
}
}
int merg (
int x,
int y)
{
int t1 =
get(x);
int t2 =
get(y);
if (t1 != t2)
//判断是否是一个歌手（判断是否为一个祖先）
{
f[t2] = t1;
//靠左原则，且路径压缩后根植也改变了
}
return 0;
}
int main ()
{
while (scanf (
"%d%d",&n,&m) !=
EOF)
{
int sum =
0;
int x,y;
init();
for (
int i=
1; i<=m; ++
i)
{
scanf ("%d%d",&x,&
y);
merg(x,y);
}
for (
int i=
1; i<=n; ++
i)
if (f[i] ==
i)
sum++
;
printf ("%d\n",sum);
}
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/10381178.html
相关资源：JAVA上百实例源码以及开源项目
