题意:找几个不相连的团体,最后查找发现只要father有几个是自己的,就有几个团队,这个我没想到
#include<stdio.h>
#include<string.h>
const int MAXN=1010;
int father[MAXN],rank[MAXN];
int hash[MAXN];
void Make_set(int n)
{
for(int i=0;i<=n;i++)
{
father[i]=i;
rank[i]=0;
}
}
int Find(int x)
{
int r=x;
while(r!=father[r])
{
r=father[r];
}
if(r!=x) father[x]=r;
return father[x];
}
void Union(int x,int y)
{
if(x==y)return;
if(rank[x]>rank[y])//让秩小的加到秩大的
{
father[y]=x;
}
else
{
if(rank[x]==rank[y])//当秩相等,令祖先的秩++
{
rank[y]++;
}
father[x]=y;
}
}
int main()
{
int T,i,j;
int n,m,a,b;
scanf("%d",&T);
while(T--)
{
memset(hash,0,sizeof(hash));
scanf("%d%d",&n,&m);
Make_set(n);
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
int x=Find(a);
int y=Find(b);
Union(x,y);
}
int total=0;
for(i=1;i<=n;i++)
{
if(father[i]==i) total++;
}
printf("%d\n",total);
}
return 0;
}