题意：现在在弄一个大学调查，调查的内容就是，大学生群体的信仰。 如果测试样例输入 1 2 就代表 1 2 拥有同样的信仰。 最后问你最多有多少个不同的 信仰。
显然这是一个并查集的题目。而且是模版题目。
传送门：POJ-2524-Ubiquitous Religions
#include <stdio.h> int pre[50005]; int Find(int x) { int r=x; while(r!=pre[r]) r=pre[r]; // 路径压缩 int i=x,j; while(pre[i]!=r) { j=pre[i]; pre[i]=r; i=j; } return r; } void mix(int x,int y) { int fx=Find(x),fy=Find(y); if(fx!=fy) pre[fy]=fx; // 左边为王 } int main() { int n,m,a,b,cnt,cas=1,i,j; while(scanf("%d%d",&n,&m) && (n || m)) { cnt = 0; // 初始化 for(i=1; i<=n; i++) pre[i] = i; for(i=0; i<m; i++) { scanf("%d%d",&a,&b); mix(a,b); } for(i=1;i<=n;i++) if(pre[i] == i) cnt++; printf("Case %d: %d\n",cas++,cnt); } return 0; }