首页 > 代码库 > POJ 2524 (简答并查集) Ubiquitous Religions
POJ 2524 (简答并查集) Ubiquitous Religions
题意:有编号为1到n的学生,然后有m组调查,每组调查中有a和b,表示该两个学生有同样的宗教信仰,问最多有多少种不同的宗教信仰
简单并查集
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 50000 + 10; 8 int parent[maxn], n, m; 9 10 int GetParent(int x)11 {12 return parent[x] == x ? x : parent[x] = GetParent(parent[x]);13 }14 15 void Init(void)16 {17 for(int i = 0; i <= n; ++i)18 parent[i] = i;19 }20 21 int main(void)22 {23 #ifdef LOCAL24 freopen("2524in.txt", "r", stdin);25 #endif26 27 int kase = 0;28 while(scanf("%d%d", &n, &m) == 2 && (m + n))29 {30 Init();31 for(int i = 0; i < m; ++i)32 {33 int a, b;34 scanf("%d%d", &a, &b);35 int pa = GetParent(a);36 int pb = GetParent(b);37 if(pa != pb)38 parent[pa] = pb;39 }40 int sum = 0;41 for(int i = 1; i <= n; ++i)42 if(parent[i] == i)43 ++sum;44 printf("Case %d: %d\n", ++kase, sum);45 }46 return 0;47 }
POJ 2524 (简答并查集) Ubiquitous Religions
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。