程序员最近都爱上了这个网站  程序员们快来瞅瞅吧!  it98k网:it98k.com

本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2021-12(24)

2022-01(11)

Python 集合法实现并查集

发布于2019-08-20 11:59     阅读(464)     评论(0)     点赞(24)     收藏(3)


一般的并查集都是用递归或者新建一个类来实现,这里介绍一种用Python的集合功能来实现的非递归非函数并查集,这个方法暂时未在其他地方见过,尤其是中文领域目前还未见过,很可能是搜索引擎无法搜索到正确内容的原因,所以不排除会有撞车的。(20190730)

假设存在N个点存在连通关系E:

N = 5, E = [[0, 1], [1, 2], [2, 3]]

求两个点的连通性,就可以使用并查集去检验:

  1. def connections(self, N: int, E: List[str], a: int, b: int) -> bool:
  2. p = {i: {i} for i in range(N)} #并查集初始化
  3. for x, y in E: #遍历边
  4. if p[x] != p[y]: #如果两个集合不相等
  5. p[x] |= p[y] #将y集合并进x集合
  6. for z in p[y]: #遍历y集合的元素
  7. p[z] = p[x] #所有y集合的元素都指向x集合
  8. return p[a] == p[b]

[a, b] 为[1, 3],返回为True

[a, b] 为[1, 4],返回为False

时间复杂度应该和常规的并查集一致,每次赋值其实都是指针赋值,相对来说计算量并不大,z层的总循环在我个人多次计数试验应该是在O(n)~O(nlog{}_{2}^{}\textrm{ }(n))这样,具体证明应参考并查集的标准证明,空间复杂度O(n),传递过程大多是传递集合的指针地址,并不增加额外空间。



所属网站分类: 技术文章 > 博客

作者:站起来

链接:https://www.pythonheidong.com/blog/article/49196/56df31e63533ccb91c93/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

24 0
收藏该文
已收藏

评论内容:(最多支持255个字符)