1213 How Many Tables(简单并查集)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1213

简单并查集,统计单独成树的数量。

代码:

 #include <stdio.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <algorithm>
#include <iostream>
#include <ctype.h>
#include <iomanip>
#include <queue>
#include <map>
#include <stdlib.h>
using namespace std; int f[];
int n,m; void init()
{
for(int i=;i<=n;i++)
f[i]=i;
} int find(int x)
{
if(x==f[x])
return f[x];
f[x]=find(f[x]);
return f[x];
} void Union(int x,int y)
{
int a=find(x);
int b=find(y);
if(a==b)
return;
f[a]=b;
} int main()
{
int t,a,b;
while(cin>>t){
while(t--){
scanf("%d %d",&n,&m);
init();
int sum=;
for(int i=;i<m;i++){
scanf("%d %d",&a,&b);
Union(a,b);
}
for(int i=;i<=n;i++){
if(i==find(i)){
sum++;
}
}
printf("%d\n",sum);
}
}
}
上一篇:SQL各种语(持续更新)


下一篇:8个web前端的精美HTML5 & CSS3效果及源码下载