POJ2524 Ubiquitous Religions(并查集)

本文主要是介绍POJ2524 Ubiquitous Religions(并查集)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

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

要点：

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

15315712

Seasonal

2524

Accepted

504K

313MS

C++

691B

2016-03-26 12:24:55

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 50050
int 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;
}

这篇关于POJ2524 Ubiquitous Religions(并查集)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---