题意：给出M对数，每组数是同一信仰，最后求总共有多少种信仰存在，不在集合中的当单个信仰
同样的水题拿来练习模板实用性。。。还是上一题的模板，一点没改，就变了一下输入输出。
不同意的请看之前发的，并学习并查集
#include <cstdio> using namespace std; const int MAXSIZE = 50002; int pre[MAXSIZE]; //根节点i,pre[i] = -num,其中num是该树的节点数目; //非根节点j,pre[j] = k,其中k是j的父节点 int Find(int x){//查找+非递归的路径压缩 int p = x; while( pre[p] > 0 ) p = pre[p]; while( x != p ){ int temp = pre[x]; pre[x] = p; x = temp; } return x; } void Union(int r1, int r2){ int a = Find(r1); int b = Find(r2); if( a == b ) return ; //加权规则合并 if( pre[a] < pre[b] ){ pre[a] += pre[b]; pre[b] = a; } else { pre[b] += pre[a]; pre[a] = b; } } void Initi(int n) { for( int i=0; i <= n; ++i ) pre[i] = -1; } int main() { //freopen("1.txt","r",stdin); int n,m; int x=1,count,temp1,temp2; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0 && m==0) break; count=0; Initi(n); for (int i=0;i<m;i++) { scanf("%d%d",&temp1,&temp2); Union(temp1,temp2); } for (int i=1;i<=n;i++) { if(pre[i]<0) count++; } printf("Case %d: %d/n",x,count); x++; } }
