题意分析

题目要求统计大学里学生信仰的不同宗教的最大可能数量。给定$n$个学生和$m$对关系（每对关系表示两名学生信仰相同宗教），最终需要计算这些关系形成的连通分量数量，即可能的不同宗教数。

解题思路

1.初始独立：初始时每个学生自成一个集合（宗教）。
2.合并关系：对每对关系$(i,j)$，合并其所在集合。
3.统计结果：最终遍历所有学生，统计根节点数量（即连通分量数），即为答案。

关键点：
路径压缩（getfa函数）优化查找效率。
合并不同集合（join函数）减少连通分量数。
最终统计根节点数目即为不同宗教数。

C++实现

cpp

#include <cstdio>
#include <cstdlib>
using namespace std;
 
int fa[50005] = {0};
 
int getfa(int x)
{
	if(fa[x] == x) return x;
	else return getfa(fa[x]);
}
 
 
void join(int x, int y)
{
	int s = getfa(x);
	int t = getfa(y);
	if(s != t)
	{
		fa[t] = s;
	}
	return;
}
 
int main()
{
	int m = 0, n = 0, a = 0, b = 0;
	int casenum = 0;
	while(scanf("%d%d", &n, &m) && !(m == 0 && n == 0))
	{
		casenum++;
		for(int i = 0; i < n; ++i) fa[i] = i;
		for(int i = 0; i < m; ++i)
		{
			scanf("%d%d", &a, &b);
			join(a, b);
		}
		int sum_ = 0;
		for(int i = 0; i < n ; ++i)//计数
		{
			if(fa[i] == i) sum_++;
		}
		printf("Case %d: %d\n", casenum, sum_);
	}
	return 0;
}