不相交集python实现

分手后的思念是犯贱 2022-07-17 02:54 184阅读 0赞

http://blog.csdn.net/u011608357/article/details/37966199

1.不相交集是解决等价关系的一种数据结构，执行合并和查找的速度都非常快，M次运行合并和查找的运行时间为（M\*logN）。

在一个集合中，对于每一对元素(a,b)，a,b∈S，对于关系R如果满足下面三个条件，则成关系R为等价关系：

(1)自反性 对于所有a∈S,aRa

(2)对称性 aRb当且仅当bRa

(3)传递性 若aRb且bRc,则aRc

有关不相交集的介绍和C语言实现，[点此查看][Link 1]

本文介绍的是不相交集的find和union操作的python实现:

**\[python\]** [ view plain][view plain] [ copy][view plain]

1.  def init(a):
2.  for i in range(0,110):
3.  a.append(-1);
4.  def unionset(root1,root2): \#按照大小求并
5.  tmp=a\[root1\]+a\[root2\];
6.  if a\[root1\]<=a\[root2\]:
7.  a\[root2\]=root1;
8.  a\[root1\]=tmp;
9.  else :
10. a\[root1\]=root2;
11. a\[root2\]=tmp;
12. 
13. def unions(root1,root2): \#按照高度求并
14. if a\[root1\]>a\[root2\]:
15. a\[root1\]=root2;
16. else:
17. if a\[root1\] is a\[root2\]: \#只有在高度相同的时候才进行合并
18. a\[root1\]=a\[root1\]-1;
19. a\[root2\]=root1;
20. 
21. def find(a,x):
22. if a\[x\]<=-1:
23. return x;
24. else :
25. return find(a,a\[x\]);
26. 
27. 
28. a=\[\]; \#测试代码
29. init(a);
30. unionset(1,2); \#按大小求并
31. unionset(3,4);
32. unions(5,6); \# 按高度求并
33. unions(5,7);
34. print find(a,2);
35. unionset(1,3);
36. print find(a,4);
37. print find(a,5);
38. print find(a,7);

[Link 1]: http://blog.csdn.net/u011608357/article/details/21806611
[view plain]: http://blog.csdn.net/u011608357/article/details/37966199#

发表评论取消回复

表情：

评论列表（有 0 条评论，184人围观）

还没有评论，来说两句吧...

相关阅读

相关并查集(不相交集)详解

目录一.并查集 1.什么是并查集 2.并查集的基本操作 3.并查集的应用 4.力扣上的题目二.三大操作 1.初始化 2.查找 3.合并三.省份数量

亦凉/ 2024年03月25日 09:43/ 0 赞/ 70 阅读

相关 LeetCode-1035. 不相交的线

目录题目思路动态规划题目来源 [1035. 不相交的线][1035.] 题目思路绘制一些连接两个数字 A\[i\] 和 B

绝地灬酷狼/ 2024年03月24日 08:28/ 0 赞/ 45 阅读

相关 Python实现不相交集算法——Alternate Disjoint Set

Python实现不相交集算法——Alternate Disjoint Set 不相交集算法，又称并查集算法，是一种用于处理动态连通性问题的数据结构。在计算机科学和网络领域中，

ゝ一纸荒年。/ 2024年03月17日 15:12/ 0 赞/ 80 阅读

相关 1035.不相交的线

1035.不相交的线题干描述解题思路代码实现题干描述 [力扣入口][Link 1] 我们在两条独立的水平线上按给定的顺序写下 A 和

Dear 丶/ 2023年10月16日 17:49/ 0 赞/ 42 阅读

相关华为OD机试真题 Python 实现【区间交集】

目录题目思路考点 Code -------------------- 题目 > 给定一组闭区间，其中部分区间存在交集。 > > 任意两个给定区间的交集

旧城等待，/ 2023年09月23日 19:27/ 0 赞/ 206 阅读

相关 python中交集_Python中的区域交集

![Image 1][] I have a code that takes a condition C as an input, and computes the solut

小鱼儿/ 2023年01月01日 05:58/ 0 赞/ 218 阅读

相关 1035. 不相交的线

2021-05-21 LeetCode每日一题链接：[https://leetcode-cn.com/problems/uncrossed-lines/][https_

浅浅的花香味﹌/ 2022年10月14日 13:53/ 0 赞/ 178 阅读

相关不相交集python实现

http://blog.csdn.net/u011608357/article/details/37966199 1.不相交集是解决等价关系的一种数据结构，执

分手后的思念是犯贱/ 2022年07月17日 02:54/ 0 赞/ 185 阅读

相关 python 字符相减得到数字

python中没有字符之间的直接相减运算，但可以通过ord()函数实现 ord()函数主要用来返回对应字符的ascii码 >>> ord('9')-ord('0'

清疚/ 2022年05月31日 09:23/ 0 赞/ 390 阅读

相关算法——不相交的线

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

短命女/ 2021年07月25日 16:03/ 0 赞/ 430 阅读