Python 集合法实现并查集
发布于2019-08-20 11:59 阅读(605) 评论(0) 点赞(24) 收藏(3)
一般的并查集都是用递归或者新建一个类来实现，这里介绍一种用Python的集合功能来实现的非递归非函数并查集，这个方法暂时未在其他地方见过，尤其是中文领域目前还未见过，很可能是搜索引擎无法搜索到正确内容的原因，所以不排除会有撞车的。（20190730）
假设存在N个点存在连通关系E：
N = 5, E = [[0, 1], [1, 2], [2, 3]]
求两个点的连通性，就可以使用并查集去检验：
- def connections(self, N: int, E: List[str], a: int, b: int) -> bool:
- p = {i: {i} for i in range(N)} #并查集初始化
- for x, y in E: #遍历边
- if p[x] != p[y]: #如果两个集合不相等
- p[x] |= p[y] #将y集合并进x集合
- for z in p[y]: #遍历y集合的元素
- p[z] = p[x] #所有y集合的元素都指向x集合
- return p[a] == p[b]
[a, b] 为[1, 3]，返回为True
[a, b] 为[1, 4]，返回为False
时间复杂度应该和常规的并查集一致，每次赋值其实都是指针赋值，相对来说计算量并不大，z层的总循环在我个人多次计数试验应该是在~
这样，具体证明应参考并查集的标准证明，空间复杂度
，传递过程大多是传递集合的指针地址，并不增加额外空间。
所属网站分类: 技术文章 > 博客
作者：站起来
链接：https://www.pythonheidong.com/blog/article/49196/56df31e63533ccb91c93/
来源：python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力