第二十五天：并查集

今天是释然发题解的第二十五天，以后会经常和大家分享学习路上的心得，希望和大家一起进步，一起享受coding的乐趣 本文约2400字，预计阅读10分钟 昨天我们学习了动态规划之线性规划，忘记的小伙伴们可以看一下哦：

动态规划之线性规划

今天我们来聊一聊并查集，明天和大家分享树的问题的相关题目：

并查集

什么是并查集？用树表示集合获取树根合并第一种：第二种：路径压缩 例题一：POJ1611问题分析树的遍历

什么是并查集？

N 个不同的元素分布在若干个互不相交集合中，需要多次进行以下3个操作：

合并a,b两个元素所在的集合 Merge(a,b)查询一个元素在哪个集合查询两个元素是否属于同一集合 Query(a,b)

用树表示集合

如何表示并查集呢？我们可以用树来表示，如果两个元素的根节点相同，就说明他们属于同一个集合，通过递归的方式从要找的元素开始寻找树根，如果找到就返回树根，没有找到就继续递归查找：

parent[i]=j;//表示元素i的父亲是j parent[i]=i;//表示i是一棵树的根节点 void initial(int *parent[],int n) { for(int i=1;i<=n;i++) { parent[i]=i; } }

获取树根

int parent[n]; //输入数据 int GetRoot(int a) //求a树根 { if(parent[a]==a) return a; return GetRoot(parent[a]); } //也可以这样写 int GetRoot(int a) //求a树根 { if( parent[a] != a) parent[a] = GetRoot(parent[a]); return parent[a]; }

合并

这里考虑两种方式：

第一种：

把深度浅的直接挂在另一棵树下面，假如说两棵树都很深但是深度一样，那么树的深度必然增加，就不够理想

第二种：路径压缩

当我们查询一个结点的时候，直接将该节点到跟路径上的每一个结点数值解挂在根的下面

Merge(a,b)//表示的是将b的树根的父亲设置为a的树根，将b合并到a Query(a，b)//比较 int parent[N]; int merge(int a,int b)//合并 { parent[GetRoot(b)] = GetRoot(a); //b的树根的父亲是a的树根 } bool Query(int a,int b)//查找只需要判断a和b在不在一个集合里面就可以啦 { return GetRoot(a) == GetRoot(b); }

接下来就是判断并查集的复杂度了，因为存储了每一个元素的父亲，所以空间复杂度是O（n），这个很好理解，而时间复杂度就是为了找到根花的时间，就是Getroot的复杂度，如果说我们使用路径压缩的存储方式，那么这个复杂度平均一下在N不是很大的时候是常数，不会超过4

例题一：POJ1611

题目链接 今年很可能会有这样的题目哦，今年新冠疫情爆发了，很可能回往这方面出题。~~我的猜测 这是翻译的题目： 就是有n个学生，编号0到 n-1, 以及m个团体，(0 < n <= 30000 , 0 <= m <= 500) 一个学生可以属于多个团体，也可以不属于任何团体。如果一个学生疑似患病，则它所属的整个团体都疑似患病。 已知0号学生疑似患病，以及每个团体都由哪些学生构成，求一共多少个学生疑似患病。

样例输入： 100 4 //100人，4团体 2 1 2 //团体有2人 编号是1和2 5 10 13 11 12 14 2 0 1 2 99 2 200 2//200人，2团体 1 5 5 1 2 3 4 5 1 0 0 0 //代表终止输入 样例输出： 4 1 1 解释如下： 总共三组测试数据 100人，4团体。200人，2团体。1人，0团体 只有当且仅当人数为0并且团体为0时终止输入，属于多组输入

问题分析

所有的互相感染的都放在一个集合里面，就是问0所在的集合有多少个元素，我们把0作为这个感染集合的根节点

int parent[MAXN+5]; int total[MAXN+5];//表示每一个集合的人数，在每一次合并的时候直接更新 //合并函数 void Merge(int a,int b) { p1=GetRoot(a); p2=GetRoot(b); if(p1==p2) return ;//不需要合并 total[p1]+=total[p2]; parent[p2]=p1;//把b的根挂到a的根 } int main() { while (true) //为了多组输入 { cin >> n >> m; if (n == 0 && m == 0) break; for (int i = 0; i < n; ++i) { parent[i] = i; total[i] = 1; } //之前这是每一组测试数据 for (int i = 0; i < m; ++i) { int h, s; scanf("%d", &k);//k个学生 scanf("%d", &h);//我们把第一个学生当做这个组的根 for (int j = 1; j < k; ++j) { scanf("%d", &s); Merge(h, s);//建树 } } printf("%d\n",total[GetRoot(0)]); } }

好了，今天的并查集就到这里。 释然每天发布一点自己学习的知识，希望1年后我们也能在ACM的赛场上见面，一起去追寻自己的程序猿之路吧！

后期也会和大家一起分享学习心得和学习经验呢，明天我们不见不散哦！

下期预告：

树的遍历

如果大家有什么建议或者要求请后台留言，释然也想和大家一起进步呀！ 联系方式：shirandexiaowo@foxmail.com