宗教信仰

• • 1526宗教信仰
• 描述
• 输入
• 输出
• 样例输入
• 样例输出
• 分析
• 代码实现
  • 觉得有用就顶起来
  • 戳我查看更多博客

1526:宗教信仰

总时间限制: 5000ms 内存限制: 65536kB

描述

世界上有许多宗教，你感兴趣的是你学校里的同学信仰多少种宗教。
你的学校有n名学生（0 < n <= 50000），你不太可能询问每个人的宗教信仰，因为他们不太愿意透露。但是当你同时找到2名学生，他们却愿意告诉你他们是否信仰同一宗教，你可以通过很多这样的询问估算学校里的宗教数目的上限。你可以认为每名学生只会信仰最多一种宗教。

输入

输入包括多组数据。
每组数据的第一行包括n和m，0 <= m <= n(n-1)/2，其后m行每行包括两个数字i和j，表示学生i和学生j信仰同一宗教，学生被标号为1至n。输入以一行 n = 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

这是OpenJudge上的一道(水)题，戳我查看

—————分析—————

有木有发现，这是图论的知识;
这是一个无向图，但是我们最终的结果是求一共有多少不同的宗教(其实也没啥区别@@滑稽@@)。
查找图中的元素呢,这里给大家推荐一个方法–>

int find(int k)
{if(t[k]==k) return k;else return t[k]=find(t[k]);
}

似不似很森气？
让我们来解析一下，这里采用递归的方式也就可以在整个可以遍历的图中
寻找，知道找不到为止，然后用数组存下来**
好，接下来自己看代码……

—————代码实现—————

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a,b,t[50005];
int find(int k)
{if(t[k]==k) return k;else return t[k]=find(t[k]);
}
int main()
{int k=0;while(++k){int ans=0,o;scanf("%d%d",&n,&m);if(!n&&!m) return 0;for(int i=1;i<=n;i++)t[i]=i;for(int i=1;i<=m;i++){scanf("%d%d",&a,&b);if(find(a)!=find(b)) t[t[a]]=t[b];}for(int i=1;i<=n;i++)if(t[i]==i) ans++;printf("Case %d: %d\n",k,ans);}return 0;
}

**

觉得有用就顶起来

**
**

戳我查看更多博客

**