Input
The input consists of a number of cases. Each case starts with a line specifying the integers n and m. The next m lines each consists of two integers i and j, specifying that students i and j believe in the same religion. The students are numbered 1 to n. The end of input is specified by a line in which n = m = 0.
Output
For each test case, print on a single line the case number (starting with 1) followed by the maximum number of different religions that the students in the university believe in.
题意：
给出n个学生，并编号1-n (0 < n <= 50000).然后对其中m个进行寻问(m个关系)，得到a b为同一个宗教信仰，然后统计总共有多少种信仰（没有出现的学生默认单独为一种）
思路：
此题就是最简单的利用并查集，我们将信仰相同的学生合并在一起（unite）然后再统计pre[i] 等于自身的个数，即为最后统计个数
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn =
100005;
int pre[maxn];
int ran[maxn];
int vis[maxn];
//用于统计是否出现过
int n,m,cnt;
int find(
int x){
if(x!=pre[x])
return pre[x] =
find(pre[x]);
else return pre[x];
}
void unite(
int x,
int y){
x = find(x),y =
find(y);
if(x!=
y){
if(ran[x]>=
ran[y]){
ran[x]++
;
pre[y] =
x;
}
else {
ran[y]++
;
pre[x] =
pre[y];
}
}
else return;
}
void init(){
for(
int i=
1;i<=n;i++
){
pre[i] =
i;
ran[i] =
0;
}
}
int main(){
cnt =
0;
while(~scanf(
"%d%d",&n,&
m)){
if(n==
0&m==
0)
break;
int ans =
0;
init();
for(
int i=
1;i<=m;i++
){
int x,y;
scanf("%d%d",&x,&
y);
unite(x,y);
}
for(
int i=
1;i<=n;i++
){
if(pre[i] == i) ans++
;
}
printf("Case %d: %d\n",++
cnt,ans);
}
}
转载于:https://www.cnblogs.com/Tianwell/p/11195071.html
