首页 > 代码库 > POJ 1611 The Suspects
POJ 1611 The Suspects
第一道并查集,听起来很高大上的样子,其实也不难理解
我感觉并查集的精髓就在那个路径压缩上面,将叶子节点直接指向根
并:将两个集合合并在一起
查:查询某个元素是否在该集合中
题意:已知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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。