问题 A: 并查集＿宗教信仰
时间限制: 1 Sec 内存限制: 128 MB提交: 15 解决: 8
[ 提交][ 状态][ 讨论版]
题目描述
世界上有许多不同的宗教，现在有一个你感兴趣的问题：找出多少不同的宗教，在你的大学中的大学生信仰了多少种不同的宗教。你知道在你的大学有n个学生（0<n<= 50000）。若直接问每一个学生的宗教信仰不大适合。此外，许多学生还不太愿意说出自己的信仰。有一种方法来避免这个问题，询问m（0<=m<=n（n- 1）/ 2）对学生，询问他们是否信仰同一个宗教（比如，可以询问他们是否都参加同一教堂）。从这个数据，您可能不知道每个人宗教信仰，但是你可以知道有多少不同宗教信仰。你可以假设，每名学生最多信仰一个宗教。
输入
输入包含多组测试数据。每组测试数据的开头包含两个整数n和m。接下来有m行，每行有两个整数i和j，编号为i和j的同学信仰同一个宗教。学生的编号从从1开始到n。当输入使n=0，m=0标志输入的结束。
输出
每组测试数据的输出只有一行，包含数据的组别（从1开始）和学生最多信仰的宗教数。
样例输入
10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10 4
2 3
4 5
4 8
5 8
0 0
样例输出
Case 1: 1
Case 2: 7
提示
#include<stdio.h>
#include<string.h>
int parent[50000+50];
int num[50000+50];
int find_root(int x)
{
return x==parent[x]?x:find_root(parent[x]);
}
int main()
{
int m,n,i,k,s,e,cnt,cas=0,n1,n2;//cas等于0放外面 别傻了
while(scanf("%d %d",&n,&m)!=EOF)
{
cnt=0;
if(!m&&!n) break;
for(i=1;i<=n;i++)
parent[i]=i;
memset(num,0,(n+5)*sizeof(num[0]));
for(i=0;i<m;i++)
{
scanf("%d %d",&s,&e);
n1=find_root(s);
n2=find_root(e);
if(n1!=n2) parent[n1]=n2;//这一步是关键
}
for(i=1;i<=n;i++)
{
k=i;
k=find_root(k);
num[k]=1;
}
for(i=1;i<=n;i++)
if(num[i]) cnt++;
printf("Case %d: %d\n",++cas,cnt);
}
return 0;
}
做了rank处理后
速度很快
#include<stdio.h>
#include<string.h>
int parent[50000+50];
int num[50000+50],used[50000+50],rank[50000+50];
int find_root(int x)
{
//return x==parent[x]?x:find_root(parent[x]);
return parent[x]==x?x:(parent[x]=find_root(parent[x]));//路径压缩 这里不一样了 多了个赋值
}
int main()
{
int m,n,i,t,s,e,cnt,cas=0,n1,n2;
while(scanf("%d %d",&n,&m)!=EOF)
{
cnt=0;
if(!m&&!n) break;
if(m==0) {printf("Case %d: %d\n",++cas,n);
continue;
}
for(i=1;i<=n;i++)
{
parent[i]=i;
num[i]=0;
used[i]=0;
rank[i]=1; //貌似初始化为几斗可以
}
scanf("%d %d",&s,&e);
used[s]=1;used[e]=1;
t=1;
parent[s]=e;
for(i=1;i<m;i++)
{
scanf("%d %d",&s,&e);
if(!used[s]) {t++;used[s]=1;} //出现没出现过的点 树增加了一棵
if(!used[e]) {t++;used[e]=1;}
n1=find_root(s);
n2=find_root(e);
if(n1!=n2)
{
if(rank[n1]>=rank[n2])
{
parent[n2]=n1;
rank[n1]+=rank[n2];
}
else
{
parent[n1]=n2;
rank[n2]+=rank[n1];
}
t--; //树合并减少了一棵
}
}
for(i=1;i<=n;i++)
if(!used[i]) t++;
printf("Case %d: %d\n",++cas,t);
}
return 0;
}