/*
如果两个学生的信仰一样 则总的宗教个数减一
*/
#include
<
iostream
>
#include
<
stdio.h
>
using
namespace
std;
int
sum,n,m;
int
father[
50001
];
void
makeset(
int
x){
for
(
int
i
=
1
;i
<=
x;i
++
) { father[i]
=
i; }}
int
findset(
int
x)
//
查
{
if
(x
!=
father[x]) { father[x]
=
findset(father[x]); }
//
回溯
return
father[x];}
void
Union(
int
a,
int
b){
int
x
=
findset(a);
int
y
=
findset(b);
if
(x
==
y)
return
; sum
=
sum
-
1
; father[y]
=
x;}
int
main(){
int
l
=
1
;
while
(scanf(
"
%d%d
"
,
&
n,
&
m)
!=
EOF) {
if
(n
==
0
&&
m
==
0
)
break
; sum
=
n; makeset(n);
int
first,second;
for
(
int
i
=
1
;i
<=
m;i
++
) { scanf(
"
%d%d
"
,
&
first,
&
second); Union(first,second); } printf(
"
Case %d: %d\n
"
,l,sum); l
++
; }
return
0
;}
已知有n个大学生，其中有m对宗教信仰相同的学生，请你估算这n个学生中最多有多少种宗教信仰。
依旧是简单的并查集应用。宗教信仰的最大值为学生数n，因此一开始把n个学生作为n个集合，对给出的每对大学生 a 和 b ，如果他们在不同的集合，就合并他们，然后宗教数减一。
这次依旧用到了路径压缩，只不过上一次写的是非递归，这次写了一个递归版本。也就是搜索完成回溯的时候"顺便"将当前节点的父节点直接指向祖先节点。题目大意解释来自Slyar Home (
www.slyar.com) 转载请注明，谢谢合作。
转载于:https://www.cnblogs.com/cyiner/archive/2011/05/16/2048229.html
