题意：

学校中每个人都有宗教信仰，现在只能知道某些人的宗教信仰相同，求总共有几种宗教

要点：

水题，跟HDU1213一毛一样，都是求最后集合个数，早知道不做了

15315712

Accepted

504K

313MS

691B

2016-03-26 12:24:55

#include
    
     #include
     
      #include
      
       #define maxn 50050int p[maxn], rank[maxn];int m, n,num;void init(){	for (int i = 1; i <= m; i++)	{		p[i] = i;		rank[i] = 0;	}}int find(int x){	if (p[x] == x) return x;	return p[x] = find(p[x]);}void merge(int x, int y){	x = find(x);	y = find(y);	if (x == y) return;	if (rank[x] > rank[y])	{		p[y] = x;		num--;	}	else	{		p[x] = y;		if (rank[x] == rank[y]) rank[y]++;		num--;	}}int main(){	int kase = 1, x, y;	while (~scanf("%d%d", &m, &n), n + m)	{		init();//初始化不能忘记		num = m;		while (n--)		{			scanf("%d%d", &x, &y);			merge(x, y);		}		printf("Case %d: %d\n", kase++,num);	}	return 0;}