SDNU 1217 CD收藏——并查集

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=1;i<=n;i++) f[i]=i;for(int i=1;i<=m;i++){cin>>x>>y;merge(x,y);}for(int i=1;i<=n;i++)if(f[i]==i) ans++;cout<<ans<<endl;
}

?