Ubiquitous Religions(POJ 2524)
~题目链接~
http://poj.org/problem?id=2524
输入
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
题目概述
1.输入学生数和调查到的案例，输入案例（同组案例信仰同一宗教），输出信仰的最大宗教数
简单并查集
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 50000+10
int flag[maxn],num=0,sum;
int find(int a)
{
if(flag[a]==a)
return a;
else
return find(flag[a]);
}
void set(int i,int j)
{
int x=find(i);
int y=find(j);
if(x==y)
return;
sum--;
if(x!=y)
flag[y]=x;
}
int main()
{
int n,m,i,j;
while(~scanf("%d%d",&n,&m) && n+m!=0)
{
num++;
sum=n;
for(int k=1; k<=n; k++)
flag[k]=k;
while(m--)
{
scanf("%d%d",&i,&j);
set(i,j);
}
printf("Case %d: %d
",num,sum);
}
return 0;
}