首页 > 代码库 > POJ 2524 (简答并查集) Ubiquitous Religions

POJ 2524 (简答并查集) Ubiquitous Religions

2024-07-21 01:48:02   214人阅读

题意：有编号为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


联系
我们