并查集

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>
#include<algorithm>
#include<string.h>
#include<set>
using namespace std;
int pre[100005],n,m;
void initial()
{
　　　for(int i = 0;i <= n;i++)
　　　　　　pre[i]=i;///因为刚开始并不知道每个的祖先节点，先将其祖先节点设为它本身，在后面的执行过程中再改变
}
int found(int x)///寻找祖先节点
{
　　if(pre[x]!=x)
　　{
　　　　pre[x]=found(pre[x]);
　　}
　　return pre[x];
}
void unite(int a,int b)///将输入的两个数放在一个分类中，如果已经在一个分类中了就不执行操作
{
　　int x=found(a);
　　int y=found(b);
　　if(x!=y)
　　{
　　　　pre[y]=x;
　　}
}
int main()
{
　　int a,b,ans;
　　while(cin>>n>>m)
　　{
　　　　ans=0;
　　　　initial();
　　　　while(m--)
　　　　{
　　　　　　cin>>a>>b;
　　　　　　unite(a,b);
　　　　}
　　　　for(int j=1;j<=n;j++)
　　　　{
　　　　　　if(pre[j]==j)
　　　　　　ans++;
　　　　}
　　　　cout<<ans<<endl;
　　}
　　return 0;
}