首页 > 代码库 > POJ 1611 The Suspects

POJ 1611 The Suspects

2024-07-19 03:48:01   220人阅读

第一道并查集，听起来很高大上的样子，其实也不难理解

我感觉并查集的精髓就在那个路径压缩上面，将叶子节点直接指向根

并：将两个集合合并在一起

查：查询某个元素是否在该集合中

 

题意：已知0号同学染病了，那么和他同在一个集合的同学也都可能染病了，输出可能染病的总人数

标准的并查集，模板题

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 30000 + 10; 8 int total[maxn], parent[maxn]; 9 int n, m, k;10 11 int GetParent(int a)12 {13     if(parent[a] != a)14         parent[a] = GetParent(parent[a]);15     return parent[a];16 }17 18 void Merge(int a, int b)19 {20     int p1 = GetParent(a);21     int p2 = GetParent(b);22     if(p1 == p2)23         return;24     total[p1] += total[p2];25     parent[p2] = p1;26 }27 28 int main(void)29 {30     #ifdef LOCAL31         freopen("1611in.txt", "r", stdin);32     #endif33 34     while(scanf("%d%d", &n, &m) == 2 && (m+n))35     {36         for(int i = 0; i < n; ++i)37         {38             parent[i] = i;39             total[i] = 1;40         }41         for(int i = 0; i < m; ++i)42         {43             int h, s, t;44             scanf("%d%d", &h, &s);45             for(int j = 1; j < h; ++j)46             {47                 scanf("%d", &t);48                 Merge(s, t);49             }50         }51         printf("%d\n", total[GetParent(0)]);52     }53     return 0;54 }
代码君

 

POJ 1611 The Suspects


联系
我们